《算法竞赛进阶指南》0x68 T1 关押罪犯

本文主要是介绍《算法竞赛进阶指南》0x68 T1 关押罪犯，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目传送门

题目描述

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;
}

这篇关于《算法竞赛进阶指南》0x68 T1 关押罪犯的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！