记录编号	73347	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.124 s
提交时间	2013-10-21 13:48:58	内存使用	1.76 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int SIZEN=20001,SIZEM=100001;
class EVENT{
public:
	int u,v;
	int w;
};
bool operator < (EVENT a,EVENT b){
	return a.w<b.w;
}
EVENT edge[SIZEM];
vector<int> c[SIZEN];
int father[SIZEN]={0};
int n,m;
void read(void){
	scanf("%d%d",&n,&m);
	int i;
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
	}
	for(i=1;i<=n;i++) father[i]=i;//初,所有人均为独立并查集
}
int grand(int x){
	if(father[x]==x) return x;
	int ans=grand(father[x]);
	father[x]=ans;
	return ans;
}
void merge(int x,int y){
	father[x]=y;
}
bool divide(int a,int b){//将a,b二人分开
	int ga,gb,nowg;
	int i;
	ga=grand(a),gb=grand(b);
	if(ga==gb) return false;
	for(i=0;i<c[a].size();i++){
		if(c[a][i]==b) continue;
		nowg=grand(c[a][i]);
		if(nowg!=gb) merge(nowg,gb);
	}
	for(i=0;i<c[b].size();i++){
		if(c[b][i]==a) continue;
		nowg=grand(c[b][i]);
		if(nowg!=ga) merge(nowg,ga);
	}
	c[a].push_back(b);
	c[b].push_back(a);
	return true;
}
int ans(void){
	int i;
	for(i=m;i>=1;i--){
		if(!divide(edge[i].u,edge[i].v)) return edge[i].w;
	}
	return 0;
}
int main(){
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	read();
	sort(edge+1,edge+1+m);
	printf("%d\n",ans());
	return 0;
}