关押罪犯(带权并查集/二分图染色)
本题有两种做法,一个是用带权并查集,一个使用二分图染色。
由于两个方法的做法思路都是殊途同归的,这里只讲一下主要思路:
某两个人在同一监狱就会发生一些冲突,我们要让两个监狱中发生冲突的最大值最小。
对于最大值最小,我们很容易的就能想到二分。因此我们可以尝试二分取最小值。
取一个中间值 $mid$,我们需要判断,将所有仇恨值不超过 $mid$ 的两个人放在同一监狱,能否合理的将所有人分在两个监狱中。
如果没法将所有人分配好,当前的仇恨值 $mid$ 都无法满足分配,那么 $0 \sim mid$ 都一定不能满足分配,因此需要扩大仇恨值,即二分右区间。否则说明当前的仇恨值 $mid$ 已经可以满足分配,由于取得是最小值,因此我们可以尝试继续缩小范围,即二分左区间,最终就会集中在一个固定值,即最终答案。
那么接下来的问题就是我们如何判断,将所有仇恨值不超过 $mid$ 的人放在同一个监狱,能否满足分配。这里既可以用染色,也可以用并查集。
如果用染色,其实两个监狱就是一个二分图的两半,我们将所有仇恨值大于 $mid$ 的两个人之间连一条边,然后看是否能成功染色即可。
如果用并查集,同样的,也要分成两部分,因此可以对所有点设置一个权值,权值有 $1$ 和 $0$,如果两个点能在同一个监狱,那么它们之间的距离模 $2$ 为 $0$,否则它们之间的距离模 $2$ 为 $1$。然后用带权并查集维护一下即可。
C++ 代码(带权并查集)
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010, M = 100010;
int n, m;
int p[N], d[N]; //带边权并查集
struct P
{
int x, y, k; //k 表示 x 和 y 的仇恨
}per[M]; //所有的边
int find(int x) //找某个点所在的集合(路径压缩优化)
{
if(x != p[x])
{
int root = find(p[x]);
d[x] ^= d[p[x]];
p[x] = root;
}
return p[x];
}
bool check(int mid) //判断将仇恨值不超过mid的人放在同一个监狱是否合法
{
memset(d, 0, sizeof d); //初始化每个点到根节点的距离
for(int i = 1; i <= n; i++) p[i] = i; //初始化每个点所在集合
for(int i = 0; i < m; i++) //枚举所有关系
if(per[i].k > mid) //如果当前关系的仇恨值超过mid,说明两个人不能在同一集合
{
int x = per[i].x, y = per[i].y;
int px = find(per[i].x), py = find(per[i].y);
if(px == py) //在同一集合
{
//两个点的异或值模2为0说明两个点在一个监狱,不合法
if(d[x] ^ d[y] == 0) return false;
}
else //不在同一集合
{
d[px] = d[x] ^ d[y] ^ 1; //要让两个点不在同一集合,两个点之间的距离模2为1
p[px] = py;
}
}
return true; //到这说明方案合法
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++)
{
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
per[i] = {x, y, k};
}
int l = 0, r = 1e9; //仇恨值范围[0, 10^9]
while(l < r) //二分
{
int mid = l + r >> 1;
if(check(mid)) r = mid; //如果当前仇恨值合法,尝试缩小范围
else l = mid + 1; //否则扩大范围
}
printf("%d\n", r);
return 0;
}
C++ 代码(二分图染色)
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20010, M = 200010;
int n, m;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int color[N]; //记录每个点所染颜色
void add(int a, int b, int c) //添加边
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int c, int mid) //染色法
{
color[u] = c;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(w[i] <= mid) continue;
if(!color[j])
{
if(!dfs(j, 3 - c, mid)) return false;
}
else if(color[j] == c) return false;
}
return true;
}
bool check(int mid) //判断是否合法
{
memset(color, 0, sizeof color); //重置颜色
for(int i = 1; i <= n; i++) //枚举每个点
if(!color[i] && !dfs(i, 1, mid)) //如果当前点没有被染色,且染色失败
return false; //不合法
return true; //否则合法
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h); //初始化邻接表
while(m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c); //无向边
}
int l = 0, r = 1e9;
while(l < r) //二分
{
int mid = l + r >> 1;
if(check(mid)) r = mid; //如果合法,就尝试缩小范围
else l = mid + 1; //否则扩大范围
}
printf("%d\n", r);
return 0;
}