我的算法书 - 网络流求解二分图匹配

摘要

本文将详细介绍如何运用网络流模型解决经典的二分图最大匹配问题。我们将从问题定义、建模思路、算法实现到复杂度分析，一步步揭示网络流的强大能力。

背景与动机

二分图匹配是图论中一个非常核心的问题，广泛应用于各种资源分配场景。例如：

任务分配：将一组任务分配给一组员工，每个员工只能执行特定的任务。
课程选择：学生和课程的匹配，每个学生有自己的课程偏好。
在线广告：广告位和广告的匹配，目标是最大化点击率。

虽然匈牙利算法是解决二分图匹配的经典专用算法，但网络流提供了一种更通用、更具扩展性的视角。理解如何用网络流解决此问题，是掌握更复杂网络流模型的关键一步。

问题定义

“二分图 (Bipartite Graph)”

一个图 $G=(V, E)$ ，如果其顶点集 $V$ 可以被划分为两个不相交的子集 $X$ 和 $Y$ ，使得每一条边 $(u, v) \in E$ 的两个端点都分别属于这两个子集（即 $u \in X, v \in Y$ ），则称该图为二分图。

“匹配 (Matching)”

在图 $G$ 中，一个匹配是指一个边的子集 $M \subseteq E$ ，其中任意两条边都没有公共的顶点。

“最大匹配 (Maximum Matching)”

一个图中，包含边数最多的匹配被称为最大匹配。

我们的目标是，给定一个二分图，找到它的最大匹配。

一句话算法

将二分图转化为一个特殊的流网络，源点连接左部顶点，右部顶点连接汇点，原图中的边转化为容量为1的有向边，网络的最大流即为二分图的最大匹配数。

关键思路：网络流建模

解决问题的核心在于如何将二分图匹配问题转化为一个最大流问题。这需要我们构建一个对应的流网络。

增加源点和汇点：
- 创建一个超级源点 S。
- 创建一个超级汇点 T。
构建网络流图：
- 从源点 S 向二分图的左部所有顶点 $u \in X$ 连一条有向边，容量为 1。这代表每个左部顶点“提供”一个匹配机会。
- 二分图中间的边保持不变，但方向从左部顶点 $u \in X$ 指向右部顶点 $v \in Y$ ，容量也为 1。这代表一个潜在的匹配选择。
- 从二分图的右部所有顶点 $v \in Y$ 向汇点 T 连一条有向边，容量为 1。这代表每个右部顶点“接受”一个匹配机会。

为什么这样可行？

流量为1的约束：网络中所有边的容量都为1。根据网络流的性质，每条边的实际流量要么是0，要么是1。
匹配与流路径的对应：
- 一条从 S 到 T 的流量为1的增广路，例如 S -> u -> v -> T，意味着我们选择了一条从 u 到 v 的匹配边。
- 由于 S 到 u 和 v 到 T 的容量都是1，所以每个顶点 u 和 v 最多只会被一条增广路经过。这恰好对应了匹配的定义：每个顶点最多只能与一条匹配边相关联。
最大流等于最大匹配：
- 我们在这个网络中寻找最大流。每找到一条增广路，就相当于找到了一个新的匹配，使得总匹配数加一。
- 当无法再找到新的增广路时，网络达到最大流。此时，流的总量就等于我们能找到的最大匹配数。这就是著名的最大流最小割定理的推论。

算法步骤

建图：根据上述建模思路，将输入的二分图转换为一个流网络。
求最大流：在该流网络上，使用标准的最大流算法（如 Dinic 或 ISAP）计算从源点 S 到汇点 T 的最大流。
输出结果：最大流的值就是二分图的最大匹配数。

复杂度分析

假设二分图的左部有 $N_1$ 个顶点，右部有 $N_2$ 个顶点，共有 $M$ 条边。

时间复杂度:
- 构建的流网络中，顶点数 $V = N_1 + N_2 + 2$ ，边数 $E = M + N_1 + N_2$ 。
- 在二分图中，使用 Dinic 算法的时间复杂度为 $O(E\sqrt{V})$ 。对于单位容量网络，Dinic 的复杂度可以优化到 $O(M\sqrt{N_1+N_2})$ 。
空间复杂度:
- 需要存储流网络的邻接表，空间复杂度为 $O(V+E)$ ，即 $O(N_1+N_2+M)$ 。

代码实现

我们将使用 Dinic 算法来实现。

cpp

copy

        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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

        #include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 1e9;

struct Edge {
    int to;
    int capacity;
    int rev; // 反向边在邻接表中的索引
};

vector<vector<Edge>> adj;
vector<int> level;
vector<int> iter;

// 增加一条从 u 到 v 容量为 cap 的边
void add_edge(int u, int v, int cap) {
    adj[u].push_back({v, cap, (int)adj[v].size()});
    adj[v].push_back({u, 0, (int)adj[u].size() - 1}); // 反向边
}

// BFS 计算层次图
bool bfs(int s, int t) {
    level.assign(adj.size(), -1);
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (const auto& edge : adj[u]) {
            if (edge.capacity > 0 && level[edge.to] < 0) {
                level[edge.to] = level[u] + 1;
                q.push(edge.to);
            }
        }
    }
    return level[t] != -1;
}

// DFS 寻找增广路
int dfs(int u, int t, int f) {
    if (u == t) return f;
    for (int& i = iter[u]; i < adj[u].size(); ++i) {
        Edge& e = adj[u][i];
        if (e.capacity > 0 && level[u] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.capacity));
            if (d > 0) {
                e.capacity -= d;
                adj[e.to][e.rev].capacity += d;
                return d;
            }
        }
    }
    return 0;
}

// 计算从 s 到 t 的最大流
int max_flow(int s, int t) {
    int flow = 0;
    while (bfs(s, t)) {
        iter.assign(adj.size(), 0);
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n1, n2, m;
    cin >> n1 >> n2 >> m;

    int s = 0, t = n1 + n2 + 1;
    adj.resize(t + 1);

    // 源点 S 连接左部顶点
    for (int i = 1; i <= n1; ++i) {
        add_edge(s, i, 1);
    }

    // 右部顶点连接汇点 T
    for (int i = 1; i <= n2; ++i) {
        add_edge(n1 + i, t, 1);
    }

    // 二分图的边
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, n1 + v, 1);
    }

    cout << max_flow(s, t) << endl;

    return 0;
}

测试用例

假设我们有以下二分图：

左部顶点: {1, 2, 3}
右部顶点: {4, 5, 6}
边: (1,4), (1,5), (2,5), (3,6)

输入:

(注意：输入时右部顶点需要相对于右部顶点集重新编号，例如4->1, 5->2, 6->3)

建图过程:

源点 S=0, 汇点 T=7。
S 连接 1, 2, 3，容量为1。
4, 5, 6 (在图中编号为 3+1, 3+2, 3+3) 连接 T，容量为1。
添加边 (1, 4), (1, 5), (2, 5), (3, 6)，容量为1。

运行结果:

一个可能的最大匹配是 {(1,4), (2,5), (3,6)}。

经典例题

1. 洛谷 P3386 【模板】二分图最大匹配

链接: Luogu P3386
描述: 裸的二分图最大匹配问题，可以直接使用上面的模板代码解决。
思路: 将题目给定的二分图转化为网络流模型，然后运行Dinic算法。

2. POJ 1274 The Perfect Stall

链接: POJ 1274
描述: 每个奶牛可以适应几个牛栏，一个牛栏只能容纳一头奶牛。求最多可以安排多少头奶牛。
思路: 典型的二分图匹配模型。奶牛是左部顶点，牛栏是右部顶点。如果一头奶牛可以适应一个牛栏，就在它们之间连一条边。问题转化为求该二分图的最大匹配。

3. HDU 2063 过山车

链接: HDU 2063
描述: 有k个小组，m个男生和n个女生。每个小组有若干男生和女生。一个男生和一个女生可以配对，如果他们来自同一个小组。求最大配对数。
思路: 这道题稍微复杂一点。男生是左部顶点，女生是右部顶点。如果一个男生和一个女生在同一个小组，就在他们之间连边。然后求最大匹配。注意，一个学生可能属于多个小组，这会影响边的建立。

实践思考与扩展

输出匹配方案: 如何修改代码来输出具体是哪几条边组成了最大匹配？
- 可以在 Dinic 结束后，遍历二分图中间的边。如果一条边 (u, v) 的容量从1变成了0，说明它被选中作为匹配边。
最小顶点覆盖: 二分图的最小顶点覆盖大小等于其最大匹配数（König定理）。
最大独立集: 二分图的最大独立集大小等于总顶点数减去最大匹配数。
带权匹配: 如果每条边有一个权重，我们想找到总权重最大的匹配，这就变成了最大权匹配问题，需要使用更复杂的算法，如 KM 算法或费用流。

目录

摘要