记录编号	122426	评测结果	AAAAAAAAAA
题目名称	[東方S3] 藤原妹红	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.406 s
提交时间	2014-09-23 15:32:17	内存使用	4.03 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <list>
#include <iterator>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <functional>
#include <deque>
#define For(i,j,k) for(int i=(j);i<=(k);i++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint;
const int INF=0x7fffffff;
const double eps=1e-6;
using namespace std;
//================struct declaration======================
struct adj
{
  int from,to;
  double len;
  adj (int from=0,int to=0,double len=0):from(from),to(to),len(len){}
  bool operator <(const adj&rhs) const
  {
     return len<rhs.len;
  }
}Edgelist[200010];
//================var declaration=-========================
const int MAXN=40010;
vector <adj> Edge[MAXN];
int n,m,ans;
bool vis[MAXN];
int siz[MAXN],root[MAXN];
double S[MAXN],sum=0;
double s2=-10;
//================function declaration====================
void dfs(int now);
double sqr(double x){return x*x;}
int findr(int x){return root[x]==x?root[x]:root[x]=findr(root[x]);}
//================main code===============================
int main()
{
  string ProgrammeName="mokou";
  string FloderName="COGS";
  freopen((ProgrammeName+".in").c_str(),"r",stdin);
  freopen((ProgrammeName+".out").c_str(),"w",stdout);
#ifdef DEBUG
  clock_t Start_Time=clock();
  system(("copy C:\\Users\\abc\\Desktop\\HouJikan\\"+FloderName+"\\standard.cpp C:\\Users\\abc\\Desktop\\HouJikan\\"+FloderName+"\\submit.txt").c_str());
#endif 
  scanf("%d%d",&n,&m);
  For(i,1,m)
    scanf("%d%d%lf",&Edgelist[i].from,&Edgelist[i].to,&Edgelist[i].len);
  sort(Edgelist+1,Edgelist+1+m);
  For(i,1,n)
    root[i]=i;
  for(int i=1,cnt=1;cnt<n;i++)
  {
    int s=Edgelist[i].from,e=Edgelist[i].to;
    double l=Edgelist[i].len;
    if (findr(s)!=findr(e))
    {
      root[findr(s)]=findr(e),cnt++,sum+=l;
      Edge[s].push_back(adj(s,e,l));
      Edge[e].push_back(adj(e,s,l));
      //printf("%d %d %lf\n",s,e,l);
    }
  }
  memset(vis,false,sizeof(vis));
  memset(S,0,sizeof(S));
  dfs(1);
  printf("%d\n",ans);
  //printf("%lf\n",s2);
#ifdef DEBUG
  clock_t End_Time=clock();
  printf("\n\nTime Used :%.6lf Ms\n",double(Start_Time-End_Time)/(-CLOCKS_PER_SEC));
#endif
  return 0;
}
//================function code===========================
void dfs(int now)
{
  int siz=Edge[now].size();
  vis[now]=true;
  double s=0;
  double ava=double(sum)/(siz);
  For(i,0,siz-1)
  {
    adj &e=Edge[now][i];
    if (!vis[e.to])
    {
       dfs(e.to);
       S[now]+=S[e.to]+e.len;
       s+=sqr(S[e.to]+e.len-ava);
    }
  }
  s+=sqr(sum-S[now]-ava);
  if (siz!=1&&(s2<0||s-s2<eps))
    s2=s,ans=now;
}