记录编号	461734	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.080 s
提交时间	2017-10-20 16:16:31	内存使用	15.57 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
const int maxn=1e6+5;
using namespace std;
struct peo
{
	int a,b,hate;
	peo(){a=b=hate=0;}
	bool operator < (const peo &A)const
	{
		return hate>A.hate;
	}
}p[maxn];
inline int get();
inline void U_N_I_O_N(int x,int y);
int find(int x);
int n,m;
int ihateset[maxn];
int main()
{
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	n=get(),m=get();
	for(int i=1;i<=2*n;i++)ihateset[i]=i;
	for(int i=1;i<=m;i++)
	{
		p[i].a=get();
		p[i].b=get();
		p[i].hate=get();
	}
	sort(p+1,p+m+1);
	for(int i=1;i<=m;i++)
	{
		if(find(p[i].a)==find(p[i].b))
		{
			printf("%d\n",p[i].hate);
			return 0;
		}
		U_N_I_O_N(p[i].a,p[i].b+n);
		U_N_I_O_N(p[i].b,p[i].a+n);
	}
	printf("0\n");
	return 0;
}
inline void U_N_I_O_N(int x,int y)
{
	ihateset[find(x)]=find(y);
}
int find(int x)
{
	if(ihateset[x]!=x)return ihateset[x]=find(ihateset[x]);
	return x;
}
inline int get()
{
	int t=0;char c=getchar(),j=1;
	while(!isdigit(c))
		if(c=='-')j=-1,c=getchar();
		else c=getchar();
	while(isdigit(c))
		t=(t<<3)+(t<<1)+c-'0',
		c=getchar();
	return j*t;
}