记录编号	41715	评测结果	AAAAAATTTT
题目名称	944.[東方S3] 藤原妹红	最终得分	60
用户昵称	Makazeu	是否通过	未通过
代码语言	C++	运行时间	4.127 s
提交时间	2012-08-10 10:22:34	内存使用	4.88 MiB

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=40010;
const int MAXM=200010;
class Edge
{
public:int u,v;double c;
}E[MAXM];
int N,M;

/*Comparison function*/
bool cmp(const Edge&a,const Edge&b)
{ return a.c<b.c;}

/*Read data from input file*/
inline void init()
{
	scanf("%d%d\n",&N,&M);
	for(int i=1;i<=M;i++)
		scanf("%d%d%lf\n",&E[i].u,&E[i].v,&E[i].c);
	sort(E+1,E+1+M,cmp);
}

/*The New Graph*/
vector<int> map[MAXN];
vector<double> val[MAXN];

/*Union-Find Set*/
int num[MAXN];
inline void merge(int a,int b) {num[b]=a;}
int find(int k){return ((k==num[k])?k:(num[k]=find(num[k])));}

/*Mini-Spanning Tree*/
inline void mst()
{
	int now=0,x,y;
	for(int i=1;i<=N;i++) num[i]=i;
	for(int i=1;i<=M;i++)
	{
		x=find(E[i].u);
		y=find(E[i].v);
		if(x==y) continue;
		merge(x,y);now++;
		map[E[i].u].push_back(E[i].v);
		map[E[i].v].push_back(E[i].u);
		val[E[i].u].push_back(E[i].c);
		val[E[i].v].push_back(E[i].c);
		if(now==N-1) break;
	}
}

double ans=1e100,res,nb,tlen[MAXN],tmplen;
const double ni=2.0;
int ansp;
int ktop,flag[MAXN],noip;

/*dfs*/
void dfs(int k)
{
	for(unsigned int i=0;i<map[k].size();i++)
	{
		if(map[k][i]!=noip) tmplen+=val[k][i];
		else tmplen+=val[k][i]*2;
		if(flag[map[k][i]])continue;
		flag[map[k][i]]=1;dfs(map[k][i]);		
	}
}

/*EnumPoint*/
inline void enumpoint()
{
	for(int i=1;i<=N;i++)
	{
		if(map[i].size()==1) continue;
		ktop=0;memset(flag,0,sizeof(flag));
		flag[i]=1; noip=i; nb=0; res=0;
		for(int j=1;j<=N;j++)
		{
			if(flag[j]) continue; 
			flag[j]=1;ktop++; 
			tmplen=0; dfs(j);
			tmplen/=2;
			tlen[ktop]=tmplen;
		}
		for(int j=1;j<=ktop;j++)
			nb+=tlen[j];
		nb/=double(ktop);
		for(int j=1;j<=ktop;j++)
			res+=(double(tlen[j])-nb)*(double(tlen[j])-nb);
		if(res<ans) {ans=res,ansp=i;}
	}		
	printf("%d\n",ansp);
}

int main()
{
	freopen("mokou.in","r",stdin);
	freopen("mokou.out","w",stdout);
	init();
	mst();
	enumpoint();
	return 0;
}