简介

二分图指的是可以把点放到两个集合中，并且集合中不存在边。染色法可以判断一个图是否为二分图，匈牙利算法可以求出二分图最大匹配。匹配指的是二分图中任意两条边都不依赖于同一个顶点的一个子图，简而言之就是在这两边连线不能重复连同一个点，求这些连线的个数。

染色法判定二分图

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

用 DFS 染色，每个节点和它的子节点颜色不能相同，染完所有节点如果没发生冲突就证明它是一个二分图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e5+10, M = 2*N;
int n, m;

// 看到 h 就要记得初始化... 被坑了好多次了
int h[N], e[M], ne[M], idx, color[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 传进来的节点一定是没染色的 否则不会被传进来
// 返回染色是否成功
bool dfs(int u, int co) {
    color[u] = co;
    int nco = 3 - co;  // co == 1 ? 2 : 1
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!color[j]) {
            if (!dfs(j, nco)) return false;
        } else if (color[j] == co) return false;  // 子节点颜色不能与父节点相同
    }
    return true;
}

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        // 只染没染过色的节点
        if (!color[i]) {
            if (!dfs(i, 1)) {
                flag = false;
                break;
            }
        }
    }
    
    if (flag) cout << "Yes";
    else cout << "No";
    
    return 0;
}

匈牙利算法

给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号 1∼n2），二分图共包含 m 条边。数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

题目链接：AcWing 861。

由于要遍历一个节点的所有子节点，所以这里用邻接表存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <bitset>
#include <cstring>
using namespace std;

const int N = 1010, M = 1e5+10;
// 我已经无数次因为忘记初始化树导致 TLE 了
int h[N], e[M], ne[M], idx;
// 右边节点 -> 左边节点
int match[N];
bitset<N> st;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 为左边的某个节点匹配
bool find(int x) {
    // 遍历所有右边的节点
    for (int i = h[x]; i != -1; i = ne[i]) {
        int j = e[i];
        // 如果当前的节点没有被尝试过
        if (!st[j]) {
            // 标记 防止下一步让被匹配的节点寻找下一个可能性时再次选到 j
            st[j] = 1;
            // 如果这个子节点还没有被匹配 或者匹配到这个子节点的可以有其它选择
            if (match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    memset(h, -1, sizeof h);
    int n1, n2, m;
    cin >> n1 >> n2 >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    int ans = 0;
    for (int i = 1; i <= n1; i++) {
        // 这里一定要先清空
        st.reset();
        ans += find(i);
    }
    cout << ans << '\n';
    return 0;
}

最大流算法

题目和上面一样，同样是求二分图的最大匹配。

关于最大流算法的模板，可以参考本站关于网络流的文章，这里简述一下如何建图。

设源点，汇点分别为 s,ts,t 对于左边的每一个点，从源点出发连一条流量为 1 的边；对于右边的每一个点，连一条到达汇点流量为 1 的边。然后左边和右边的每一条边都连一条流量为 1 的边。每一个可行流都是一个合法匹配，所以这里就是求最大流，用 Dinic 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1010, M = 600010;
int n1, n2, m, S = 1, T = 2, INF = 1e8;
int h[N], e[M], ne[M], f[M], idx;
int d[N], cur[N], q[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], f[idx] = c, h[a] = idx++;
}

bool bfs() {
    memset(d, -1, sizeof d);
    int hh = 0, tt = 0;
    q[0] = S, d[S] = 1, cur[S] = h[S];
    
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1 && f[i]) {
                d[j] = d[t] + 1;
                cur[j] = h[j];
                if (j == T) return true;
                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int lim) {
    if (u == T) return lim;
    
    int flow = 0;
    for (int i = cur[u]; ~i && flow < lim; i = ne[i]) {
        cur[u] = i;
        int j = e[i];
        if (f[i] && d[j] == d[u] + 1) {
            int t = find(j, min(f[i], lim - flow));
            if (!t) d[j] = -1;
            f[i] -= t, f[i^1] += t, flow += t;
        }
    }
    return flow;
}

int dinic() {
    int r = 0, flow;
    while (bfs()) {
        while (flow = find(S, INF)) r += flow;
    }
    return r;
}

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &n1, &n2, &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        a += 2;
        b += n1 + 2;
        if (!st[a]) st[a] = true, add(S, a, 1), add(a, S, 0);
        if (!st[b]) st[b] = true, add(b, T, 1), add(T, b, 0);
        add(a, b, 1), add(b, a, 0);
    }
    
    printf("%d\n", dinic());
    return 0;
}

关押罪犯（判断二分图）

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

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

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

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

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

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

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

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

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

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

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

题目链接：AcWing 257，P1525。

既然是求一个最大值的最小值，第一想法是二分答案判断合法性，那么判断合法性的方式就是看严格大于二分出来结果的所有边能否构成一个二分图。如果能构成二分图，两边的点就不在同一个集合中，满足要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <cstring>
using namespace std;

const int N = 20010, M = 200010;

int h[N], e[M], ne[M], w[M], idx;
int n, m;
int color[N];


void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool dfs(int u, int co, int p) {
    color[u] = co;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (w[i] <= p) continue;
        if (color[j] && color[j] == co) return false;
        if (!color[j] && !dfs(j, -co, p)) return false;
    }
    return true;
}

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

    return true;
}


int main() {
    cin >> n >> m;
    
    int l = 0, r = 0;
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
        r = max(r, c);
    }
    
    while (l < r) {
        int mid = l+r>>1;
        if (check(mid)) r = mid;
        else l = mid+1;
    }
    cout << l << endl;
    return 0;
}