记录编号	52366	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.229 s
提交时间	2013-02-03 17:42:32	内存使用	2.02 MiB

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