记录编号	133229	评测结果	EEEEE
题目名称	公路建设	最终得分	0
用户昵称	笑一炮	是否通过	未通过
代码语言	C++	运行时间	0.584 s
提交时间	2014-10-27 16:49:09	内存使用	2.30 MiB

#include <iostream>
#include <string.h>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("road.in");
ofstream fout("road.out");

const int maxn=510,INF=1<<30;
int n,m,siz[maxn],fa[maxn],temp,from,to;
double sum=0,d[maxn][maxn],dis;

int min(int a,int b) {	return a<b? a:b;	}

int findfa(int x)
{
	if (fa[x]==x)	return x;
	else 
	{
		temp=fa[x];
		fa[x]=findfa(fa[x]);
		siz[temp]-=siz[x];
		if (temp==fa[x]) siz[fa[x]]+=siz[x];
	}
	
}
void merge(int a,int b)
{
	a=findfa(a),b=findfa(b);
	if (a!=b)
	{
		fa[a]=b;
		siz[b]+=siz[a];
	}
}
void prim(int s)
{
	bool done[maxn];
	int ss=1,min;
	double p[maxn];
	memset(done,0,sizeof(done));
	done[s]=true;
	p[0]=INF;
	for (int i=1;i<=n;i++)
		if (!done[i] && d[s][i]!=INF)	p[i]=d[s][i];
		else p[i]=INF;
	sum=0;
	while (ss!=n)
	{
		min=0;
		for (int i=1;i<=n;i++)
			if (!done[i] && p[i]<p[min]) min=i; 
		if (min==0) break;
		ss++;
		sum+=p[min];
		done[min]=true;
		for (int i=1;i<=n;i++)
			if (!done[i] && p[i]>d[min][i])
						p[i]=d[min][i];
	}
}
int main()
{
	fin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		fa[i]=i;
		siz[i]=1;
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			d[i][j]=INF;
	bool k=false;
	fout<<setiosflags(ios::fixed)<<setprecision(1);
	for (int a=1;a<=m;a++)
	{
		fin>>from>>to>>dis;
		d[from][to]=d[to][from]=min(d[from][to],dis);
		merge(from,to);
		if (!k)
		{
			if (siz[findfa(1)]==n)
			{
				k=true;
				prim(1);	
				fout<<sum/2<<endl;
				continue;
			}
			fout<<'0'<<endl;
		} 
		else
		{
			prim(1);
			fout<<(sum/2)<<endl;
		}
	}
	return 0;

}