记录编号	47248	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.667 s
提交时间	2012-10-31 15:44:28	内存使用	2.03 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#include <vector>
#include <queue>
using namespace std;

struct datatype
{
	int a,b,c;
}data[100010];

int m,waynum[20010];
bool in[20010],in1[20010];
vector<int> wayto[20010],waycost[20010];
queue<int> que;

void swap(datatype& a,datatype& b)
{
	datatype temp;
	temp=a;
	a=b;
	b=temp;
}

void qqsort(int l,int r)
{
	int ll,rr,temp;
	ll=l;
	rr=r;
	temp=data[(l+r)>>1].c;
	while (ll<rr)
	{
		while (data[ll].c<temp)
			ll++;
		while (temp<data[rr].c)
			rr--;
		if (ll<=rr)
		{
			swap(data[ll],data[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(l,rr);
	if (ll<r)
		qqsort(ll,r);
}

bool bfs(int ys,int lim)
{
	int i,pos,to,cost;
	while (!que.empty())
		que.pop();
	que.push(ys);
	in[ys]=true;
	while (!que.empty())
	{
		pos=que.front();
		for (i=0;i<waynum[pos];i++)
		{
			cost=waycost[pos][i];
			if (cost<=lim)
				continue;
			to=wayto[pos][i];
			if (in[to])
			{
				if ((in1[to]&&in1[pos])||(!in1[to]&&!in1[pos]))
					return(false);
			}
			else
			{
				in[to]=true;
				in1[to]=!in1[pos];
				que.push(to);
			}
		}
		que.pop();
	}
	return(true);
}

bool check(int limpos)
{
	int i;
	bool flag;
	memset(in,0,sizeof(in));
	memset(in1,0,sizeof(in1));
	for (i=limpos+1;i<=m;i++)
	{
		if (!in[data[i].a])
		{
			flag=bfs(data[i].a,data[limpos].c);
			if (flag==false)
				return(false);
			i=limpos;
		}
		else if (!in[data[i].b])
		{
			flag=bfs(data[i].b,data[limpos].c);
			if (flag==false)
				return(false);
			i=limpos;
		}
	}
	return(true);
}

int main(void)
{
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	int i,n,l,r,mid;
	bool ok;
	cin>>n>>m;
	for (i=1;i<=m;i++)
	{
		cin>>data[i].a>>data[i].b>>data[i].c;
		waynum[data[i].a]++;
		waynum[data[i].b]++;
		wayto[data[i].a].push_back(data[i].b);
		wayto[data[i].b].push_back(data[i].a);
		waycost[data[i].a].push_back(data[i].c);
		waycost[data[i].b].push_back(data[i].c);
	}
	qqsort(1,m);
	l=0;
	r=m;
	mid=(l+r)>>1;
	while (l<r)
	{
		ok=check(mid);
		if (ok)
			r=mid;
		else
			l=mid+1;
		mid=(l+r)>>1;
	}
	cout<<data[mid].c<<endl;
	return(0);
}