AcWing 257. 关押罪犯

一、二分图的三个等价关系

• 二分图
• 奇数环
• 染色时不出现矛盾

二、二分图判定

其实对于二分图判定的做法还是比较好想的，也易于实现

由于本题要求把罪犯划分到两个监狱中（我理解为划分到两个不同的集合中）那么我不禁想到图论的二分图

首先，抛来一个二分图的定义：

如果一张无向图的\(n\)个节点(\(n>=2\))可以分为\(A\),\(B\)两个集合，

且满足$A ∩ B = ? \(，而且在**同一集合内的点之间都没有边相连**，那么这张无向图被称为**二分图**，其中\)A\(和\)B$分别叫做二分图的左部和右部

那么对于本题，我们就是要把所有人分为两个部分，其间不出现矛盾，显然很符合二分图的要求

别太高兴，问题来了：如何判定这个“矛盾图”是不是二分图

在这里，本人抛出一个二分图判定定理：

一张无向图是二分图：

当且仅当图中不存在奇环（奇环是指长度为奇数的环）

既然有了判定定理，我们就可以使用染色法进行二分图判定

染色法基本实现如下：

1.大多数情况基于\(dfs\)（深度优先搜索）

但本题本人用了\(bfs\)实现（害怕爆系统栈）

2.我们尝试用黑和白两种颜色标记图中的点，当一个节点被标记了，那么所有与它相连的点应全部标记为相反的颜色

如果在标记过程中出现冲突，那么算法结束，证明本图中存在奇环，即本图不为二分图；反之，如果算法正常结束，那么证明本图是二分图

那好啦，现在有了染色法判定二分图，那么我们还需要考虑一件事：这个最小矛盾值怎么求？

首先，我们考虑这样一个判定问题：是否存在一种分配方案，使得最小的矛盾值不超过\(mid\)。显然，当\(mid\)较小时可行的方案对于\(mid\)较大时依然可行。换言之，本题的答案具有单调性，可以采用二分的方法求解，将求最小值问题转换为判定问题

策略如下：我们二分答案，设当前二分的值为\(mid\)，此时任意两个矛盾双方\(x\)和\(y\)必须被分在两个不同集合中，将罪犯们作为节点，在矛盾值大于等于\(mid\)的罪犯之间连一条边，我们得到一张无向图。此时我们只需判定这张无向图是否为二分图即可（因为要分为两部分），如果是二分图，令二分右端点\(R=mid\)，否则令\(L=mid\)即可

1、dfs染色法

#include 

using namespace std;
const int N = 20010, M = 200010;
int n, m;
int color[N]; //二分图的标记数组
//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
//是不是一个合法的二分图
// u:节点号 c:颜色，1：黑，2：白 3-c：互转, limit:最小冲突值
bool dfs(int u, int c, int limit) {
    color[u] = c;                       //染色为c
    for (int i = h[u]; ~i; i = ne[i]) { //枚举每条出边
        if (w[i] <= limit) continue;    //不关心小于limit冲突值的关系
        int j = e[i];
        if (color[j]) {                      //如果j染过色
            if (color[j] == c) return false; //并且与u一样，那就冲突了
        } else if (!dfs(j, 3 - c, limit))    //如果没有染过色，并且在后续的染色过程中出现冲突，也就是无法成为合法二分图
            return false;                    // 染色失败
    }
    return true; //染色成功
}

//使用limit做为最小的冲突值，这样划分的两个图是不是二分图
bool check(int limit) {
    //清空二分图的标记数组
    memset(color, 0, sizeof color);
    //这里一般都是枚举每个节点，然后找突破口
    for (int i = 1; i <= n; i++)
        if (color[i] == 0) //如果没有标记过
            //将i这个点标识为黑色:1
            if (!dfs(i, 1, limit)) //存在冲突，不是二分图,返回false
                return false;
    return true; //没有冲突,是二分图
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int a, b, c;
    for (int i = 0; i < m; i++) {
        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;
    }
    //输出最小的匹配值
    printf("%d\n", l);
    return 0;
}

2、bfs染色法

#include 

using namespace std;
const int N = 20010, M = 200010;
typedef pair PII;
int n, m;
int color[N]; //二分图的标记数组
//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
// bfs实现
bool bfs(int u, int limit) {
    //假设 1:黑，2：白，这样方便理解一些
    color[u] = 1;
    queue q;   //两个属性：节点号，颜色
    q.push({u, 1}); //将节点u入队列,颜色为黑

    while (q.size()) {
        PII t = q.front();
        q.pop();
        int u = t.first, c = t.second;
        //找到这个节点关联的其它节点
        for (int i = h[u]; ~i; i = ne[i]) {
            if (w[i] <= limit) continue; //不关心小于limit冲突值的关系
            int j = e[i];
            //没染色就染成相反的颜色
            if (!color[j]) {
                color[j] = 3 - c;
                //并且把这个新的节点入队列，再探索其它的相邻节点
                q.push({j, 3 - c});
            } else if (color[j] == c)
                return false;
            //染过的，有两种情况，一种是与本次要求的染色一样，一种是不一样，
            //不一样就是矛盾
        }
    }
    return true;
}
//使用limit做为最小的冲突值，这样划分的两个图是不是二分图
bool check(int limit) {
    //清空二分图的标记数组
    memset(color, 0, sizeof color);
    //这里一般都是枚举每个节点，然后找突破口
    for (int i = 1; i <= n; i++)
        if (color[i] == 0) //如果没有标记过
            //将i这个点标识为黑色:1
            if (!bfs(i, limit)) //存在冲突，不是二分图,返回false
                return false;
    return true; //没有冲突,是二分图
}

int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    int a, b, c;
    for (int i = 0; i < m; i++) {
        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;
    }
    //输出最小的匹配值
    printf("%d\n", l);
    return 0;
}