记录编号	175598	评测结果	AAAAA
题目名称	公路建设	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.943 s
提交时间	2015-08-06 14:50:56	内存使用	0.40 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
int totnum,tot,head[502],fa[502];
int n,m,x,y;
struct dd
{
	int kaishi,zhong,juli;
	int id;
}jie[5000];
int comp1(const dd &a,const dd &b)
{
	return a.juli<b.juli;
}
int find(int x)
{
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
inline int in()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	return x;
}
bool KUR(int t){
    sort(jie+1,jie+t+1,comp1);
	int num=0;
    totnum=0;
	memset(head,0,sizeof(head));
	for(int j=1;j<=n;++j) fa[j]=j;
	for(int j=1;j<=t;++j)
	{   int hi=jie[j].kaishi;
	    int hj=jie[j].zhong;
	    int yu=find(hj);
	    int lin=find(hi);
		if(yu!=lin)
		{
			fa[yu]=lin;
			totnum+=jie[j].juli;
			num++;
		}
		if(num==n-1)
		  return true;
	}
	return false;
}
int main()
{   freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	n=in();
	m=in();
	for(int i=1;i<=m;++i)
	{
	     jie[i].kaishi=in();
		 jie[i].zhong=in();
		 jie[i].juli=in();
		jie[i].id=i;
		if(i<n-1)
		{
			printf("0\n");
			continue;
		}
		else
		{
			if(!KUR(i)){
				printf("0\n");
				continue;
			}
			else{
				double fg=(double)totnum/2;
				printf("%.1lf\n",fg);
			}
		}
	}
}