二分图问题

二分图：「在一个图中，可以把所有的点划分到两个集合，满足所有的边都在两个集合之间连通」，我们认为这个图是「二分图」。

如果点a与点b连通，a属于集合A，那么b就必须属于集合B。如果b也属于集合A，则a和b在集合A内部连通，就不是二分图。

示例中，「绿色框所有的边都在两个集合之间连通，所以是二分图」；而「黄色框中点f和点i组成的边在集合2内部连通」，因此「黄框不是二分图」。

二分图的性质

「奇数环」：一个环的边是奇数，则为奇数环。

「存在奇数环的图不是二分图，二分图一定不存在奇数环。」

我们可以使用「反证法」来证明：

「假设一个图是二分图，那么连通的点都分布在不同的集合中。现在该图中以点a为原点存在一个奇数环，那么如下图连通之后会发现a与e连通，但是a和e同属于集合1，与假设不符。」

染色法判定二分图

染色法的概念其实就是把两个集合看做不同的颜色，比如集合1是黑色，集合2是白色。

那么按照二分图的关键性质，对于任意一个点的颜色确定之后，就能确定所有与它连通的点的颜色（与它连通的点必定与它不同色）。

所以我们遍历整个图，给所有的点都染上颜色，如果没有出现冲突，则说明是二分图。

AcWing 257. 关押罪犯

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

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

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

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

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

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

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

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

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

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

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

「输入格式」 第一行为两个正整数 N 和 M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的 M 行每行为三个正整数 aj，bj，cj，表示 aj 号和 bj 号罪犯之间存在仇恨，其怨气值为 cj。

数据保证 1≤aj<bj<N,0<cj≤109 且每对罪犯组合只出现一次。

「输出格式」 输出共 1 行，为 Z 市长看到的那个冲突事件的影响力。

如果本年内监狱中未发生任何冲突事件，请输出 0。

「数据范围」

N≤20000,M≤100000

「输入样例」

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

「输出样例」

3512

题目描述

把每个罪犯看做一个点，则两名罪犯可以连成一条边，两名罪犯之间的“元气值”就是这条边的权重。两个监狱可以看做两个不同的集合，目标就是「把所有的点分布在两个集合内，并且让集合各自的内部点所连成边的最大权重越小越好」。

题目分析

回到题目中，可以发现我们在题目描述中抽象出的模型，与二分图的模型非常相像。

局长的目的其实就是「找到一个临界点x，x是集合内所有边的最大值（注意这句话，意思就是如果某条边的权值比x大，那它就在两个集合之间，而不能在集合内部），那么所有权值大于x的边就一定能组成二分图」。

进而，我们可以「推出x左边的所有边不满足二分图，而右边的所有边满足二分图。以最终x为基准，左右两边，具有二段性，因此可以二分答案」，来找到x。

Code

// check(mid)  表示能否把仇恨值大于mid的罪犯分到两个监狱里面。
// 我们把仇恨值大于mid的分在左右两边，看有没有冲突，即使用染色法求二分图。
#include <iostream>
#include <cstring>

using namespace std;

const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], ne[M], w[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 ++ ;
}

// dfs染色 u是当前待染色的点 c代表颜色 mid是二分的中位数
bool dfs(int u, int c, int mid) {
    color[u] = c; // 染色
    // 遍历当前点的所有边
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (w[i] <= mid) continue; // 不用管mid以下的点
        if (color[j]) {
        // 如果临点已经染色 则判断是否冲突 既 临点颜色不能与当前点一样
            if (color[j] == c) return false;
        }
        else if (!dfs(j, 3 - c, mid)) return false; // 未染色则递归染色
    }
    return true;
}

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

int main() {
    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;
    }
    printf("%d\n", r);
    return 0;
}