AcWing257 关押罪犯
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目大意
\(\qquad\)给定一张正权无向图，定义冲突值为一个集合内权值最大的边，将一张图上的点，分成两部分，不同部分的点在原图上的边作废，求最小化最大冲突值，并输出。
解题思路
1. 二分答案 + 二分图判定
\(\qquad\)由于要求最小化最大冲突值，遇到最大值最小化的问题，经验上可以采用二分答案求解，具体步骤就是二分出这个最大冲突值，要使一个冲突值合法，应该有如下性质；
\(\qquad\)所以我们的问题就可以转化成：在原图的基础上将所有权值大于 \(mid\) 的点中间连边，建新图，然后判定新图是否为二分图即可，如果是二分图，代表满足 \(check\) 条件。
\(\qquad\)然后我们要求的是最小化，所以应该采用这个二分模板
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
采用的是染色法判定二分图，模板如下
bool dfs(int cur, int c, int mid)
{
clr[cur] = c;
for (int i = h[cur]; ~i; i = ne[i])
{
int j = e[i];
if (w[i] <= mid) continue ;
if (clr[j] && clr[j] == c) return false;
if (!clr[j] && !dfs(j, 3 - c, mid)) return false;
}
return true ;
}
完整AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e6 + 10;
int h[N], e[N], ne[N], w[N], idx;
int clr[N], u, v, c, n, m;
void add(int a, int b, int c)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}
bool dfs(int cur, int c, int mid)
{
clr[cur] = c;
for (int i = h[cur]; ~i; i = ne[i])
{
int j = e[i];
if (w[i] <= mid) continue ;
if (clr[j] && clr[j] == c) return false;
if (!clr[j] && !dfs(j, 3 - c, mid)) return false;
}
return true ;
}
bool check(int mid)
{
memset(clr, 0, sizeof clr);
for (int i = 1; i <= n; i ++ )
if (!clr[i]) if (!dfs(i, 1, mid))
return false;
return true ;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
scanf("%d%d%d", &u, &v, &c);
add(u, v, c), add(v, u, 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;
}
扩展域并查集
\(\qquad\)还是二分答案，但是我们可以换一种思路来看，对于一条权值大于 \(mid\) 的边上的两个点\(u, v\) 我们是期望在不同的部分（监狱）的，那么这种关系显然是具有传递性的，也就是（我们称呼这样的\(u,v\)为敌人）敌人的敌人是朋友，所以我们可以想到有并查集来维护，遇到上述边\(u,v\)，如果\(u,v\)在同一集合内，逻辑冲突，\(check\)不成立，否则将\(u\)的敌人和\(v\)合并，\(v\)的敌人和\(u\)合并。
\(\qquad\)为了方便扫描我们用一个结构体数组存储图，和最小生成树一样。
完整AC代码
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, m, p[N << 1];
struct Edge
{
int u, v, w;
} edge[1000010];
int find(int x)
{
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
bool check(int mid)
{
for (int i = 1; i <= N << 1; i ++ ) p[i] = i;
for (int i = 1; i <= m; i ++ )
{
if (edge[i].w > mid)
{
int pa = find(edge[i].u), pb = find(edge[i].v);
if (pa == pb) return false;
p[pa] = find(edge[i].v + n);
p[pb] = find(edge[i].u + n);
}
}
return true ;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[i] = {u, v, w};
}
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;
}
带边权并查集
\(\qquad\)维护一下边权，把所有符合性质的点加到同一个集合里面，维护一个边权，边权和模\(2\)得到\(0\)代表在同一个集合里面，\(check\)不成立，由于\(xor\)是不进位的二进制加法，所以用异或运算代替加法和模。
判断的时候对于同一个集合里面的元素，如果边权和\(\% 2=0\)那么证明两个这样的罪犯在一个监狱，不可以，返回\(false\)，如果一路下来没错误，返回\(true\)
完整AC代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int n, m, p[N], d[N];
struct Edge
{
int u, v, w;
} edge[1000100];
int find(int x)
{
if (x == p[x]) return x;
int root = find(p[x]);
d[x] ^= d[p[x]], p[x] = root;
return p[x];
}
bool check(int mid)
{
memset(d, 0, sizeof d);
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 1; i <= m; i ++ )
{
if (edge[i].w > mid)
{
int x = edge[i].u, y = edge[i].v;
int px = find(x), py = find(y);
if (px == py)
if (d[x] ^ d[y] == 0) return false;
if (px != py)
d[px] = d[x] ^ d[y] ^ 1, p[px] = py;
}
}
return true ;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i ++ )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[i] = {u, v, w};
}
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;
}
算法对比
时间：带边权\(<\)扩展域\(<\)二分图
\(143ms<464ms<620ms\)
代码复杂度：扩展域\(<\)带边权\(<\)二分图
思维复杂度：扩展域\(<\)二分图\(<\)带边权
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |