题目传送门

题目描述

S 城现有两座*，一共关押着 N 名罪犯，编号分别为 1∼N。

他们之间的关系自然也极不和谐。

很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。

我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。

如果两名怨气值为 c 的罪犯被关押在同一*，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。

每年年末，警察局会将本年内*中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。

公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。

他准备将罪犯们在两座*内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。

假设只要处于同一*内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

题解

二分这个最大的怒气值，如果两个人之间的怒气值要比这个二分的值大，那他们显然要关在不同的*中，这样就有了很多条限制关系，即比mid大的怒气值的两人不能在同一*中，由于只有两个*，我们可以利用二分图的判定，去判断能不能满足以上所有条件，如果可以，那么怒气值就可以为mid，否则则不能，通过这样的判定再去二分，就可解决此问题

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int vis[N],n,m;
struct node
{
	int nxt,val,to;
}edge[2*N];
int head[N],tot;
void Lian(int x,int y,int z)
{
	tot++;
	edge[tot].nxt=head[x];
	edge[tot].to=y;
	edge[tot].val=z;
	head[x]=tot;
}
bool dfs(int x,int color,int lim)
{
	vis[x]=color;
	for(int i=head[x];i;i=edge[i].nxt)
	{
		if(edge[i].val<=lim) continue;
		int y=edge[i].to;
		if(!vis[y]&&!dfs(y,3-color,lim)) return 0; //这里有一个致命细节，不能直接返回dfs（y,3-color,lim），只有它等于0时才可向上传递，结束dfs，如果等于1，还需继续判断
		else if(vis[y]==color) return 0;	
	}	
	return 1;
}
bool check(int x)
{	
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
		if(!vis[i])
			if(!dfs(i,1,x))
				return 0;
	return 1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		Lian(x,y,z);
		Lian(y,x,z);
	}
	int l=0,r=1e9,ans;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d",ans);
	return 0;
}