记录编号	229220	评测结果	AAAAA
题目名称	公路建设	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.780 s
提交时间	2016-02-20 07:06:04	内存使用	0.25 MiB

#include<cstdio>
#include<algorithm>
using namespace std;

int N,M,root[510]={0},p;
struct EDGE{
	int from;
	int to;
	int w;
};
EDGE edges[2100]={0};

int Read()
{
	char ch=getchar();
	int a=0;
	while(ch<'0'||ch>'9')	ch=getchar();
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a;
}

inline int cmp(const EDGE& a, const EDGE& b)
{
	return a.w<b.w;
}

inline int FindRoot(int a)
{
	if(root[a]!=a)	root[a]=FindRoot(root[a]);
	return root[a];
}

inline void Union(int a, int b)
{
	a=FindRoot(a),b=FindRoot(b);
	root[a]=b;
}

inline void Init()
{
	for(int i=1;i<=N;i++)	root[i]=i;
}

void Kru()
{
	Init();
	int cnt=0;
	float ans=0;
	sort(edges+1,edges+1+p,cmp);
	for(int i=1;i<=p;i++){
		if(FindRoot(edges[i].from)!=FindRoot(edges[i].to)){
			Union(edges[i].to,edges[i].from);
			cnt++;
			ans+=edges[i].w;
		}
		if(cnt==N-1){
			printf("%.1f\n",ans/2);
			return;
		}
	}
	printf("0\n");
}
                                                                                                                                                 
int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	N=Read();
	M=Read();
	for(p=1;p<=M;p++){
		edges[p].from=Read();
		edges[p].to=Read();
		edges[p].w=Read();
		Kru();
	}
	return 0;
}