记录编号	57092	评测结果	AAAAA
题目名称	公路建设	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.239 s
提交时间	2013-04-06 08:55:22	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
#include<iomanip>
using namespace std;
//注意:顶点下标是0~n-1,不是1~n
const int VSIZE=501,ESIZE=2000;//顶点数和边数的范围
int n;//顶点
class SIDE{
public:
	int a,b;//连接的定点
	double t;//权值(完成时间)
};
SIDE e[ESIZE];//边
bool cmp(SIDE x,SIDE y){
	return x.t<y.t;
}
void Kruskal(int m){
	double c[VSIZE][VSIZE]={0};
	int area[VSIZE]={0};//这是并查集......这是并查集......
	deque<int> member[VSIZE];//每个域里都有什么
	double ans=0;
	int carde=0;//图里加进去的边数,是card(E)(这个坑爹的card......)
	int i;
	int x,y;
	for(i=0;i<n;i++) member[i].push_back(i),area[i]=i;//每个顶点都是一个域
	for(i=0;i<m&&carde<n-1;i++){
		x=area[e[i].a],y=area[e[i].b];
		if(x!=y){//把边加进去
			c[e[i].a][e[i].b]=c[e[i].b][e[i].a]=e[i].t;
			ans+=e[i].t;
			//cout<<ans<<" ";
			carde++;
			while(!member[y].empty()){//连接两个联通块
				member[x].push_back(member[y].front());
				area[member[x].back()]=x;
				member[y].pop_front();
			}
		}
		else if(e[i].t<c[e[i].a][e[i].b]){
			ans-=c[e[i].a][e[i].b],ans+=e[i].t;
			c[e[i].a][e[i].b]=c[e[i].b][e[i].a]=e[i].t;
		}
	}
	if(carde==n-1) cout<<ans<<endl;
	else printf("0\n");
}
void insert(int x){
	SIDE temp;
	int i=x;
	while(e[i].t<e[i-1].t&&i>0){
		temp=e[i],e[i]=e[i-1],e[i-1]=temp;
		i--;
	}
}
int main(){
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	int m;
	scanf("%d%d",&n,&m);
	cout<<setiosflags(ios::fixed)<<setprecision(1);
	int i;
	int x,y;
	double t;
	for(i=0;i<m;i++){
		scanf("%d%d%lf",&x,&y,&t);
		e[i].a=x-1,e[i].b=y-1,e[i].t=t/2;
	}
	for(i=1;i<n-1;i++) printf("0\n");
	sort(e,e+n-1,cmp);
	for(i=n-1;i<=m;i++){
		insert(i-1);
		Kruskal(i);
	}
	return 0;
}