记录编号	532325	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	LGLJ	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2019-05-28 19:44:48	内存使用	1.78 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cctype>
#define I inline
#define R register
#define LL long long
using namespace std;
int n,m;
int pre[40050]={0};
pair<int,pair<int,int> >num[100010];
I int read()
{
	int x=0;
	char ch=0;
	bool w=true;
	while(!isdigit(ch)){if(ch=='-')w=false;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return w?x:-x;
}
I int find(int x)
{
	return pre[x]==x?x:pre[x]=find(pre[x]);
}
I void join(int u,int v)
{
	int x=find(u),y=find(v);
	pre[x]=y;
}
I int MAIN()
{
	freopen ("prison1.in","r",stdin);
	freopen ("prison1.out","w",stdout);
	n=read(),m=read();
	for(R int i=1;i<=2*n;++i)
		pre[i]=i;
	for(R int i=1;i<=m;++i)
		num[i].second.first=read(),num[i].second.second=read(),num[i].first=-read();
	sort(num+1,num+m+1);
	for(R int i=1;i<=m;++i)
	{
		int u=num[i].second.first,v=num[i].second.second;
		int x=find(u),y=find(v);
		if(x==y)
		{
			cout<<-num[i].first;
			return 0;
		}
		else
		{
			join(u,v+n);
			join(u+n,v);
		}
	}
	cout<<0;
	return 0;
}
int lglj=MAIN();
int main(){;}