记录编号	226620	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.288 s
提交时间	2016-02-18 10:01:52	内存使用	1.63 MiB

#include<cstdio>
#include<algorithm>
const int maxn = 100000 + 10 ;
struct Node{
	int from,to,dis;
	Node(){dis = -1;}
}G[maxn];
inline int max(const int a,const int b){return a>b? a:b;}
inline int min(const int a,const int b){return a<b? a:b;}
int n,m,cnt;
char ch;
void read(int &x){
	x=0;
	while(ch=getchar(),ch<'!');
	while(x=x*10+ch-'0',ch=getchar(),ch>'!');
}
bool cmp(const Node& a,const Node& b){
	return a.dis < b.dis ;
}
int p[maxn],ans;
inline int find(int x){return p[x]==x?x:p[x]=find(p[x]);}
void Kruskal(){
	for(int i=1;i<=n;i++) p[i] = i;
	std::sort(G+1,G+1+m,cmp);
	for(int i=1;i<=m;i++){
		int x = find(G[i].from);
		int y = find(G[i].to );
		if( x == y ) continue;
		p[x] = y;
		ans = max(ans,G[i].dis);
		cnt++;
		if(cnt == n-1){printf("%d",ans);return;}
	}
	printf("-1");
}
int main(){	
	freopen("roada.in","r",stdin);
	freopen("roada.out","w",stdout);
	read(n);read(m);
	for(int i=1;i<=m;i++){
		read(G[i].from);
		read(G[i].to);
		read(G[i].dis);
	}
	Kruskal();
	return 0;
}