最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

实时：AcWing257 关押罪犯

来源：博客园


(资料图)

题目大意

\(\qquad\)给定一张正权无向图，定义冲突值为一个集合内权值最大的边，将一张图上的点，分成两部分，不同部分的点在原图上的边作废，求最小化最大冲突值，并输出。

解题思路

1. 二分答案 + 二分图判定

\(\qquad\)由于要求最小化最大冲突值，遇到最大值最小化的问题，经验上可以采用二分答案求解，具体步骤就是二分出这个最大冲突值，要使一个冲突值合法，应该有如下性质；

\[\large 所有权重比这个冲突值大的边两旁的点要被\]\[\large 分开到两个地方,这样才能保证这是最大冲突值\]

\(\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 #include #include 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 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 #include 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\)代码复杂度：扩展域\(<\)带边权\(<\)二分图

思维复杂度：扩展域\(<\)二分图\(<\)带边权

关键词： 采用的是 应该采用 最小生成树