记录编号	294646	评测结果	AAAAA
题目名称	公路建设	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.764 s
提交时间	2016-08-12 16:14:00	内存使用	0.22 MiB

#include<stdio.h>
#include<stdlib.h>
#define M 510
inline void read(int&x)
{
	int flag=1;
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9') if(ch=='-') flag=-1;
	x=(ch^'0');
	while(ch=getchar(),ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^'0');
	x*=flag;
}
//===============================================================
struct road{
	int from,to;
	double cost;
}dis[5000];
int cmp(const void*x,const void*y)
{
	struct road *a=(road*)x;
	struct road *b=(road*)y;
	return a->cost>b->cost?1:-1;
}
int p[M],n,m;
int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
inline double Kruskal()
{
	double ans=0;
	int i,cnt=0;
	for(i=1;i<=n;i++) p[i]=i;
	qsort(dis+1,m,sizeof(road),cmp);
	for(i=1;i<=m;i++){
		int x=dis[i].from,y=dis[i].to;
		int fx=find(x),fy=find(y);
		if(fx!=fy){
			cnt++;
			ans+=dis[i].cost;
			p[fx]=fy;
		}
		if(cnt==n-1) break;
	}
	if(cnt!=n-1) ans=0;
	return ans;
}
int _521()
{
#define STRAT
#ifdef STRAT
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
#else
	freopen("1.in","r",stdin);
#endif
	int i,k,a,b,c;
	read(n),read(k);
	for(i=1;i<=k;i++){
		read(a),read(b),read(c);
		dis[++m].from=a,dis[m].to=b,dis[m].cost=(double)c/2.0;
		double ans=Kruskal();
		if(ans==0) printf("0\n");
		else printf("%.1lf\n",ans);
	}
	return 0;
}
int _520=_521();
int main(){;}