记录编号	271262	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	Janis	是否通过	通过
代码语言	C++	运行时间	0.521 s
提交时间	2016-06-15 19:58:58	内存使用	4.45 MiB

#include<cstdio>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n,m,f[40003],x,y;
struct pr
{
	int a,b,c;
}w[100001];
 
int cmp(const pr &a,const pr &b){return a.c>b.c;}
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
int main() 
{
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>w[i].a>>w[i].b>>w[i].c;
	for(int i=1;i<=n*2;i++)f[i]=i;
	sort(w+1,w+m+1,cmp);
	for(int i=1;i<=m;i++){
		x=find(w[i].a);
		y=find(w[i].b);
		if(x==y){
			cout<<w[i].c;
			return 0;
		}
		f[y]=find(w[i].a+n);
		f[x]=find(w[i].b+n);
	}
    cout<<0;
    return 0;
}
/*4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884*/