记录编号	76424	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	ranto	是否通过	通过
代码语言	C++	运行时间	0.130 s
提交时间	2013-10-30 19:19:34	内存使用	0.31 MiB

#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("prison1.in");
ofstream out("prison1.out");

struct node
{
	long anger;
	int a;
	int b;
};

inline bool operator<(node r,node h)
{
	return (r.anger<h.anger);
}

inline bool operator>(node r,node h)
{
	return (r.anger>h.anger);
}

int n,m;
node *s;
int *f,*e;//f[i] : friend, e[i] : enemy

inline int findrootf(int a)
{
	register int itemp(a);
	while(f[itemp]!=itemp)
	{
		itemp=f[itemp];
	}
	return itemp;
}

int main()
{
	in>>n>>m;
	s=new node [m];
	f=new int [n+1];
	e=new int [n+1];
	for(int i=0;i!=m;++i)
	{
		int a,b,l;
		in>>a>>b>>l;
		s[i].a=a;
		s[i].b=b;
		s[i].anger=l;
	}
	stable_sort(s,s+m,greater<node>());
	for(int i=1;i!=n+1;++i)
	{
		f[i]=i;
		e[i]=0;
	}
	int ret(0);
	for(int i=0;i!=m;++i)
	{
		register int ai=s[i].a;
		register int bi=s[i].b;
		if(findrootf(ai)!=findrootf(bi))
		{
			if(e[ai]==0&&e[bi]==0)
			{
				e[ai]=bi;
				e[bi]=ai;
				continue;
			}
			if(e[ai]==0)
			{
				f[ai]=findrootf(e[bi]);
				e[ai]=findrootf(bi);
				continue;
			}
			if(e[bi]==0)
			{
				f[bi]=findrootf(e[ai]);
				e[bi]=findrootf(ai);
				continue;
			}
			f[findrootf(ai)]=findrootf(e[bi]);//把自己朋友的根节点连到对方的敌人的根节点上
			f[ai]=findrootf(e[bi]);//把自己连到对方敌人的根节点上
			f[findrootf(e[ai])]=findrootf(bi);//把自己敌人的朋友的根节点连到对方的朋友的根节点上
			continue;
		}
		ret=s[i].anger;
		break;
	}
	out<<ret<<endl;
	return 0;
}