记录编号	214657	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	0.158 s
提交时间	2015-12-17 13:22:43	内存使用	1.45 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node{
	int a,b,c;
};
node a[100001];
int fa[40002];
bool cmp(node a,node b)
{
	return a.c>b.c;
}
int find(int x)
{
	/*if(fa[x]==x)
		return x;
	int i=x,j=x;
	while(fa[i]!=i)
		i=fa[i];
	while(fa[x]!=j)
	{
		j=fa[x];
		fa[x]=i;
		x=j;
	}*/
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

int main()
{
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	int n,m,fx,fy;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=40001;i++)
		fa[i]=i;
	/*for(int i=1;i<=m;i++)
		printf("%d %d %d\n",a[i].a,a[i].b,a[i].c);*/
	for(int i=1;i<=m;i++)
	{
		//printf("%d %d ",a[i].a,a[i].b);
		//printf("【%d】",fa[22]);
		fx=find(a[i].a);
		fy=find(a[i].b);
		//printf("%d %d",fx,fy);
		if(fx==fy)
		{
			printf("%d",a[i].c);
			goto loop;
		}
		fa[fx]=find(a[i].b+n);
		fa[fy]=find(a[i].a+n);
		//printf(" %d %d\n",fa[fx],fa[fy]);
	}
	printf("0");
	loop:
	return 0;
}