记录编号	175624	评测结果	AAAAA
题目名称	公路建设	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.190 s
提交时间	2015-08-06 15:28:44	内存使用	0.31 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct bian
{
	int u,v,id;
	double w;
	inline friend bool operator <(bian a,bian b)
	{
		return a.w<b.w;
	}
}o;
vector<bian>a;
int n,m,u,v,shu,fa[1111];
double ans;
inline int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
int main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%lf",&o.u,&o.v,&o.w);
		o.w/=2;
		o.id=i;
		a.insert(upper_bound(a.begin(),a.end(),o),o);
		if(i<n-1)
		{
			printf("0\n");
			continue;
		}
		else
		{
			ans=0;shu=0;
			for(int j=1;j<=n;++j)
				fa[j]=j;
			for(int j=0;j<i;++j)
			{
				u=find(a[j].u);
				v=find(a[j].v);
				if(u!=v)
				{
					fa[v]=u;
					ans+=a[j].w;
					++shu;
					if(shu==n-1)
						break;
				}
			}
			if(shu==n-1)
				printf("%.1lf\n",ans);
			else
				printf("0\n");				
		}
	}
}