关押罪犯

原题链接

题目描述

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

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

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

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

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

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

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

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

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

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

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

---

染色法+二分

将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。

那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。

我们在 \([0,10^9]\) 之间枚举最大边权 \(limit\)，当 \(limit\) 固定之后，剩下的问题就是：

判断能否将所有点分成两组，使得所有权值大于 \(limit\) 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 \(limit\) 的边构成的新图是否是二分图。

判断二分图可以用染色法，时间复杂度是 \(O(N+M)\)，其中 \(N\) 是点数，\(M\) 是边数。

为了加速算法，我们来考虑是否可以用二分枚举 \(limit\)， 假定最终最大边权的最小值是 \(Ans\):

• 那么当 \(limit∈[ans,10^9]\) 时，所有边权大于 \(limit\) 的边，必然是所有边权大于 \(Ans\) 的边的子集，因此由此构成的新图也是二分图。
• 当 \(limit∈[0,ans−1]\) 时，由于 \(ans\) 是新图可以构成二分图的最小值，因此由大于 \(limit\) 的边构成的新图一定不是二分图。
• 所以整个区间具有二段性，可以二分出分界点 \(ans\) 的值。

代码

#include <bits/stdc++.h>
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 limit) {
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i]) {
        if (w[i] <= limit) continue;
        int j = e[i];
        if (color[j] != -1) {
            if (color[j] == c) return false;
        } else if (!dfs(j, !c, limit)) return false;
    }

    return true;
}

bool check(int limit) {
    memset(color, -1, sizeof color);
    for (int i = 1; i <= n; i++)
        if (color[i] == -1) {
            if (!dfs(i, 0, limit))
                return false;
        }

    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        cin >> 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;
    }

    cout << l << endl;

    return 0;
}