记录编号	227089	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.284 s
提交时间	2016-02-18 14:56:20	内存使用	10.56 MiB

#include<cstdio>
#include<algorithm>
using namespace std;

int M,N,root[1100]={0},ans=0;
struct EDGE{
	int to; 
	int from; 
	int w;
}edges[1000100]; 

int Read()
{
	char ch=getchar();
	int a=0;
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		a=a*10+ch-'0';
		ch=getchar();
	}
	return a;
}

inline int FindRoot(int a)
{
	if(root[a]==a) return a;
	root[a]=FindRoot(root[a]);
	return root[a];
}

inline void Union(int a, int b)
{
	a=FindRoot(a);
	b=FindRoot(b);
	root[a]=b;
}

inline bool compare(const struct EDGE& a, const struct EDGE& b)
{
	return a.w<b.w;
}

void Kru()
{	
	sort(edges+1,edges+1+M,compare);
	int cnt=0;
	for(int i=1;i<=M;i++){
		if(FindRoot(edges[i].from)!=FindRoot(edges[i].to)){
			Union(edges[i].from,edges[i].to);
			if(ans<edges[i].w)	ans=edges[i].w;	
			cnt++;
		}
		if(cnt==N-1){
			printf("%d",ans);return ;
		}
	}
	printf("-1");
}

int main()
{
	freopen("roada.in","r",stdin);
	freopen("roada.out","w",stdout);
	N=Read(),M=Read();
	for(int i=1;i<=N;i++)	root[i]=i;
	for(int i=1;i<=M;i++){
		edges[i].from=Read();
		edges[i].to=Read();
		edges[i].w=Read();
	}

	Kru();
	return 0;
}