记录编号	228921	评测结果	AAAAA
题目名称	公路建设	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.704 s
提交时间	2016-02-19 20:44:29	内存使用	0.36 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int ufs[505];
int find(int x){
	if(x==ufs[x])return ufs[x];
	return ufs[x]=find(ufs[x]);
}
void link(int a,int b){
	ufs[find(a)]=find(b);
}
struct edge{
	double w;int from,to;
	bool operator <(const edge a)const{
		return w<a.w;
	} 
}lst[4500];int len;
void insert(int a,int b,double w){
	lst[len].from=a;
	lst[len].to=b;
	lst[len].w=w;
	len++;
}
int n,m;
double mst(){
	for(int i=1;i<=n;++i)ufs[i]=i;
	sort(lst,lst+len);
	double ans=0;int cnt=0;
	for(int i=0;i<len;++i){
		int a = lst[i].from,b=lst[i].to;
		if(find(a)!=find(b)){
			cnt++;ans+=lst[i].w;
			link(a,b);
		}
	}
	if(cnt!=n-1)return 0;
	return ans;
}
int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%d %d",&n,&m);
	int a,b,c;
	while(m--){
		scanf("%d %d %d",&a,&b,&c);
		insert(a,b,c/2.0);
		double ans = mst();
		if(ans!=0)printf("%.1lf\n",ans);
		else printf("0\n",ans);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}