我的算法书 - 匈牙利算法

一句话算法

匈牙利算法就是让左部点一个个找匹配；如果目标右部点已经被占用，就沿着已匹配边递归“腾位置”，每找到一条增广路，匹配数就加一。

问题模型

给定一个二分图 $G=(X,Y,E)$ ：

左部点集合 $X$ ，大小为 $n$ ；
右部点集合 $Y$ ，大小为 $m$ ；
边 $(u,v)$ 表示左部点 $u$ 可以匹配右部点 $v$ ；
每个点最多只能参与一条匹配边。

目标是选择尽量多条边，使这些边两两没有公共端点。这个最大数量叫做二分图最大匹配。

“匹配与增广路”

匹配是一组互不相交的边。增广路是一条从未匹配左部点出发、到未匹配右部点结束的交替路径，路径上的边按“未匹配边、已匹配边、未匹配边……”交替出现。

核心直觉

可以把左部点看成学生，右部点看成座位。一名学生想坐某个座位：

如果座位没人坐，直接匹配成功。
如果座位已经有人坐，就问当前占座的人能不能换到别的座位。
如果当前占座的人能换走，这个座位就空出来，新学生匹配成功。
如果沿着这条链一直找到一个空座位，整条链都可以重新安排，匹配数增加 $1$ 。

这条“重新安排以后多坐下一个人”的链，就是增广路。

vis[v] 的含义也要按这个直觉理解：在一次 dfs(u) 的协商过程中，右部点 $v$ 只需要问一次。问过一次仍然无法让这轮协商成功，再问只会重复同一段递归。

算法步骤

用邻接表存二分图，只从左部点连向右部点。
维护 match[v]，表示右部点 $v$ 当前匹配的左部点；0 表示还没有匹配。
依次枚举每个左部点 $u$ 。
每次尝试前清空 vis，表示这是一轮新的增广路搜索。
执行 dfs(u)：
- 枚举 $u$ 能连到的右部点 $v$ ；
- 若 $v$ 本轮已经访问过，则跳过；
- 若 $v$ 未匹配，令 match[v] = u，搜索成功；
- 若 $v$ 已匹配，则递归尝试让 match[v] 去找别的右部点；
- 若对方能换走，也令 match[v] = u，搜索成功。
每次 dfs(u) 成功，答案加 $1$ 。

“为什么每轮都要清空 vis”

vis 不是全局的“这个右部点以后都不能碰”，而是当前左部点搜索增广路时的防重复标记。下一名左部点开始搜索时，之前问不动的右部点可能因为匹配状态已经变化而重新有用，所以必须清空。

算法证明

证明只需要记住一个核心定理：如果当前匹配不是最大匹配，那么一定存在一条增广路。

一次成功 DFS 的效果

dfs(u) 成功时，说明从未匹配左部点 $u$ 出发，沿着“未匹配边、已匹配边”交替递归，最终找到一个未匹配右部点。

把这条路径上的边状态整体翻转：
- 原来没选的边变成匹配边；
- 原来已选的边被移出匹配。
路径首尾都是未匹配点，所以未匹配边比匹配边多一条，翻转后匹配数增加 $1$ 。
一次失败 DFS 的含义

dfs(u) 失败，表示从这个左部点出发，所有可能的右部点都已经尝试过，仍然找不到未匹配右部点，也无法通过递归让别人换走。也就是说，以 $u$ 为起点的增广路不存在。
整体最优性

算法枚举所有左部点。只要还能找到增广路，某次 dfs 就会成功并让匹配数增加。枚举结束后，不存在任何从未匹配左部点出发的增广路。

根据增广路定理：没有增广路 $\Rightarrow$ 当前匹配已经是最大匹配。

复杂度分析

设左部点数为 $n$ ，右部点数为 $m$ ，边数为 $E$ 。

每次 dfs 最多访问每个右部点一次，并扫描相关边，最坏为 $O(E)$ 。
外层枚举 $n$ 个左部点。
总时间复杂度为 $O(nE)$ ，常写作 $O(VE)$ 。
空间复杂度为 $O(n+m+E)$ 。

DFS 版匈牙利算法代码短、容易写，适合 $n,m$ 在几千级别的普通二分图匹配题。若点边规模达到 $10^5$ 级别，应考虑 Hopcroft-Karp 或网络流。

代码实现

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

// 二分图最大匹配：左部点编号 1..n，右部点编号 1..m。
// dfs(u) 尝试给左部点 u 找到一个右部匹配点。
struct Hungarian {
    int n, m;
    vector<vector<int>> g;
    vector<int> match;
    vector<int> vis;

    Hungarian(int n, int m) : n(n), m(m), g(n + 1), match(m + 1, 0), vis(m + 1, 0) {}

    void add_edge(int u, int v) {
        if (u < 1 || u > n || v < 1 || v > m) return;
        g[u].push_back(v);
    }

    bool dfs(int u) {
        for (int v : g[u]) {
            if (vis[v]) continue;
            vis[v] = 1;

            // v 为空，或 v 当前匹配的左部点可以被挪到别处。
            if (match[v] == 0 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
        return false;
    }

    int max_matching() {
        int ans = 0;
        fill(match.begin(), match.end(), 0);

        for (int u = 1; u <= n; u++) {
            fill(vis.begin(), vis.end(), 0);
            if (dfs(u)) ans++;
        }
        return ans;
    }
};

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

    int n, m, e;
    cin >> n >> m >> e;

    Hungarian solver(n, m);
    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        solver.add_edge(u, v);
    }

    cout << solver.max_matching() << '\n';
    return 0;
}

测试用例

输入：

输出：

解释：

左部点 $1$ 可以匹配右部点 $1$ 或 $2$ ；
左部点 $2$ 可以匹配右部点 $2$ ；
左部点 $3$ 可以匹配右部点 $3$ 。

一种最大匹配是 $(1,1),(2,2),(3,3)$ ，所以答案为 $3$ 。

再看一个需要“腾位置”的例子：

输出：

如果一开始 $1$ 匹配了右部点 $1$ ，当 $2$ 也想匹配 $1$ 时，算法会尝试让 $1$ 改去 $2$ ，于是得到 $(2,1),(1,2)$ 。

应用分类详解

匈牙利算法的本质是：在二分图中不断寻找增广路，用局部调整换来整体匹配数增加。

一、基础二分图最大匹配

典型模式： 两类对象之间有可行关系，每个对象最多配对一次。

识别信号： 题面出现“最多配多少对”“每个人一个任务”“每个物品只能分给一个人”。

核心建模： 两类对象分别放在左右部，可行关系连边，答案就是最大匹配数。

应用场景	经典题目	核心思路
二分图匹配模板	luogu-P3386	左右部直接建图，求最大匹配
飞行员配对	luogu-P2756	两类飞行员配对，可配对关系连边
牛和牛栏分配	牛栏分配类题	奶牛能进哪些牛栏就连哪些边

二、网格图黑白染色后的匹配

典型模式： 网格上相邻格子之间放置、覆盖或互斥。

识别信号： 网格、上下左右相邻、每个格子最多使用一次、求最多可选边或最多配对。

核心建模： 按棋盘黑白染色把格子分成左右部，相邻可配对的格子连边。

应用场景	经典题目	核心思路
骨牌覆盖	网格覆盖类题	黑格连白格，匹配边表示放一块骨牌
方格取数变体	方格取数类题	相邻冲突可转成二分图覆盖或网络流
骑士共存	骑士攻击类题	骑士攻击关系在染色图中连边

三、二分图覆盖与独立集

典型模式： 不只要求匹配数，还要求最小点覆盖、最大独立集。

识别信号： “最少选点覆盖所有边”“最多选点且互不冲突”，并且冲突图是二分图。

核心建模： 先求最大匹配，再用二分图定理转化：

最小点覆盖数 $=$ 最大匹配数；
最大独立集数 $=$ 点数 $-$ 最大匹配数。

应用场景	经典题目	核心思路
最小点覆盖	机器调度类题	用 König 定理把覆盖数转为匹配数
最大独立集	二分冲突图选点类题	总点数减最大匹配数
行列覆盖模型	小行星/行列覆盖类题	行和列做左右部，一个障碍点是一条边

四、DAG 最小路径覆盖

典型模式： 在有向无环图中，用尽量少的路径覆盖所有点。

识别信号： DAG、每个点恰好被覆盖一次、路径之间不相交、求最少路径条数。

核心建模： 把每个点拆成左部 $u_{out}$ 和右部 $u_{in}$ 。原图边 $u\to v$ 变成二分图边 $u_{out}\to v_{in}$ 。每选一条匹配边，相当于把两条路径接成一条。

应用场景	经典题目	核心思路
最小路径覆盖	luogu-P2764	答案为 $n-\text{最大匹配数}$
DAG 链覆盖	DAG 路径覆盖类题	拆点后跑二分图最大匹配
任务先后连接	任务调度类题	能从一个任务接到另一个任务就连边

经典例题

1. luogu-P3386

二分图最大匹配模板题。输入已经给出左右部点数和边，直接套匈牙利算法即可。重点是每次搜索前清空 vis，并且只维护右部点的 match。

2. luogu-P2756

飞行员配对方案问题。把一类飞行员放左部，另一类飞行员放右部，可配对关系连边，最大匹配数就是最多能组成的飞行员配对数。

3. luogu-P2764

DAG 最小路径覆盖。先把每个点拆成左右两个点，原有向边转成二分图边，再求最大匹配。每条匹配边把两条路径合并成一条，所以答案是 $n-\text{最大匹配数}$ 。

参考

二分图匹配的增广路定理
König 定理