记录编号	130721	评测结果	AAAAAAAAAA
题目名称	[東方S3] 藤原妹红	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.386 s
提交时间	2014-10-23 06:13:08	内存使用	5.65 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct www{
	int b,e;
	double l;
	bool operator < (const www&x)const{return l<x.l;}//按长度排序 
} a[200001];
double length[80000],END_num[80000],aiky,aria,misaki,riki,v,zui=1e20;
int to[80000]={0},next[80000]={0},head[40001]={0},fa[40001]={0},outsum[40001]={0},n,m,i,p,zj1,zj2,zj3,zj4,lsum=0,setsum,answer;
int father(int x)
{
	if(x==fa[x])return x;
	else return fa[x]=father(fa[x]);//求父亲节点同时修改父亲节点到根节点 
}
void get_MST()
{
	setsum=n;aiky=0;//aiky存储mst总长度 
	for(i=1;i<=n;i++)fa[i]=i;
	for(i=0;i<m;i++)
	{
		zj1=a[i].b;zj3=father(zj1);
		zj2=a[i].e;zj4=father(zj2);
		if(zj3!=zj4)
		{
			setsum--;//集合数减一 
			fa[zj4]=zj3;
			
			lsum++;to[lsum]=zj2;//连接表 
			next[lsum]=head[zj1];
			head[zj1]=lsum;
			length[lsum]=a[i].l;
			
			lsum++;to[lsum]=zj1;
			next[lsum]=head[zj2];
			head[zj2]=lsum;
			length[lsum]=a[i].l;
			
			outsum[zj1]++;
			outsum[zj2]++;//出度数量 
			aiky+=a[i].l;
			if(setsum==1)break;
		}
	}
}
void init()
{
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)
	scanf("%d%d%lf",&a[i].b,&a[i].e,&a[i].l);
	sort(a,a+m);
}
double pre_dfs(int x,int y)//x为当前节点，y为其父亲节点 
{
	if(outsum[x]==1)//x出度唯一 ,为叶子节点 
	{
		END_num[head[x]]=aiky;
		return 0;//length[head[x]];//遇到叶子节点，返回与叶子节点相连的边权 
	}
	int temp;//temp记录到父亲节点的边的编号 
	double zjsum=0;//zjsum记录除父亲节点外所有END_num的值， END_num为此条边连接的集合的所有边权和 
	for(int h=head[x];h;h=next[h])
	if(to[h]!=y)
	{
		END_num[h]=pre_dfs(to[h],x)+length[h];
		zjsum+=END_num[h];
	}
	else temp=h;
	END_num[temp]=aiky-zjsum;//得到x到y的End_num 
	return zjsum;
}
void work()
{
	//zj1=1;
	//while(outsum[zj1]==1)zj1++;//找到不为叶子节点的节点 
	for(i=head[1];i;i=next[i])
	END_num[i]=pre_dfs(to[i],1)+length[i];//递归求出所有集合边权和 
	for(i=1;i<=n;i++)//删除某节点 
	if(outsum[i]!=1)
	{
		aria=aiky;misaki=0;//赋初值 
		aria/=outsum[i];//平均数 
		for(p=head[i];p;p=next[p])
		{
			riki=END_num[p]-aria;
			misaki+=riki*riki;
		}
		if(misaki<zui)
		{
			zui=misaki;
			answer=i;
		}
	}
}
int main()
{
	freopen("mokou.in","r",stdin);
	freopen("mokou.out","w",stdout);
	init();//输入函数 
	get_MST();//得到最小生成树
	//printf("%lf\n",aiky);
	work();//主工作函数 
	printf("%d\n",answer);
	return 0;
}