# 二分图最大匹配：增广路、Kőnig 定理与增量维护 ## 本节目标 学完后，你应能从“左右对象一一配对”建二分图，证明增广路算法，使用 Kőnig 定理把最小点覆盖转成最大匹配，并在只增边的过程中复用已有匹配维护最大可行前缀。 ## 前置知识与课前自测 前置：二分染色、DFS、集合覆盖。 1. 当前匹配不是最大时，必然存在什么结构？ 2. 一条增广路翻转匹配/非匹配边后，匹配大小改变多少？ 3. 二分图最小点覆盖大小与最大匹配大小有什么关系？一般图也成立吗？
自测答案 1. 从未匹配左点到未匹配右点、边交替的增广路（Berge 引理）。 2. 增加 1；路径上非匹配边比匹配边多一条。 3. 二分图中相等，这是 Kőnig 定理；一般图不成立。
## 问题动机与核心知识 贪心给每个左点随便挑一个空右点会被早期选择卡住。增广路允许“把旧配对挪走”：沿非匹配边前进、沿匹配边回到另一个左点，最终到空右点后整体翻转。 朴素 Kuhn 算法每轮从一个左点 DFS，复杂度 $O(VE)$；适合几百到几千规模。更大稀疏图应学习 Hopcroft–Karp：BFS 同时建立最短增广层次，DFS 批量增广，复杂度 $O(E\sqrt V)$。 Kőnig 定理的一个构造证明：从所有未匹配左点沿“左到右走非匹配边、右到左走匹配边”搜索，设可达集合为 $Z$，则最小点覆盖为 $$ (L\setminus Z)\cup(R\cap Z), $$ 其大小等于匹配数。 ## 实现指南 - `match_right[v]` 表示右点当前匹配的左点；每轮 DFS 重置右侧访问标记。 - 递归重配时先标记右点，避免交替环无限递归。 - 多组输入要重置匹配数组。 - 动态删除通常逆序变成加边；已有匹配在加边后仍合法，只需尝试新的增广路。 ## 精选例题 1：The Perfect Stall ### 来源信息与题意 - VJudge：[POJ-1274 The Perfect Stall](https://vjudge.net/problem/POJ-1274) - 原来源：USACO - 大致难度：匹配模型建立；考点：Kuhn 增广路 多组数据，至多 200 头牛和 200 个牛栏。每头牛给出愿意进入的牛栏，每牛、每栏至多匹配一次，求最大分配数。
Hint 1牛为左点，牛栏为右点，意愿为边。
Hint 2对每头牛寻找一条增广路；遇到已占牛栏时，递归尝试迁走原牛。
### Editorial 与证明 逐个左点做 DFS 增广。若找到空右点或能递归为原匹配左点找到替代，就把当前左点配到该右点。每次成功匹配数加一；当所有未匹配左点都无增广路时，由 Berge 引理当前匹配最大。规模 200，$O(NE)$ 足够。 ### 核心伪代码与参考实现附件 ```text match_right[stall] = unmatched for each cow u: clear visited stalls DFS through acceptable stalls: take an empty stall, or recursively move its currently matched cow count successful augmentations ``` 完整 GNU C++17 参考实现见附件：[POJ-1274.cpp](../../参考实现/07-二分图/POJ-1274.cpp) ### 复盘与变式 若每头牛和牛栏有配对收益且要求总收益最大，变成带权二分匹配；单纯优先选收益最大边不正确。 ## 精选例题 2：Asteroids ### 来源信息与题意 - VJudge：[POJ-3041 Asteroids](https://vjudge.net/problem/POJ-3041) - 原来源：USACO 2005 November Gold - 大致难度：提高；考点：最小点覆盖 = 最大匹配 $N\le500$ 的网格有 $K\le10^4$ 个小行星。一次射击可清除整行或整列，求清除全部小行星的最少射击数。
Hint 1把每一行视为左点、每一列视为右点；小行星是连接其行列的边。
Hint 2选择一行/列开火，就是选择一个端点覆盖关联边；目标是最小点覆盖。
Hint 3二分图 Kőnig 定理把答案变成最大匹配大小。
### Observations、Editorial 与证明 每颗小行星对应行—列边，开火集合必须覆盖所有边，反之任一点覆盖给出清除方案。因此答案是最小点覆盖大小；Kőnig 定理说明它等于最大匹配。用 Kuhn 求匹配，复杂度 $O(NE)$，这里至多约五百万级有效扫描。 ### 核心伪代码与参考实现附件 ```text rows are left vertices; columns are right vertices each asteroid adds a row-column edge maximum_matching = Kuhn(graph) output maximum_matching # equals minimum vertex cover by Konig ``` 完整 GNU C++17 参考实现见附件：[POJ-3041.cpp](../../参考实现/07-二分图/POJ-3041.cpp) ### 复盘与变式 若行列射击费用不同，变成二分图最小权点覆盖，可用最小割；Kőnig 的“只比较数量”不再直接给答案。 ## 精选例题 3：Maximize Mex ### 来源信息与题意 - VJudge：[CodeForces-1139E Maximize Mex](https://vjudge.net/problem/CodeForces-1139E) - 原题：[Codeforces Round 548 (Div. 2)](https://codeforces.com/problemset/problem/1139/E) - 难度：2400；考点：mex 前缀匹配、逆序加边、增量增广 $n\le5000$ 名学生属于 $m\le n$ 个社团，每人有潜力 $p_i<5000$。每天一人永久退社；退社后从每个社团至多选一人，最大化所选潜力多重集的 mex。输出每天删除后的最大 mex。
Hint 1mex 至少为 $x$，当且仅当潜力 $0..x-1$ 能分别匹配到不同社团。
Hint 2左点是潜力值，右点是社团；活跃学生提供一条潜力—社团边。
Hint 3删除难维护，逆序处理：从所有指定删除完成后的图开始，逐个把学生加回。
Hint 4已有匹配在加边后仍合法；只需反复尝试当前第一个未匹配潜力 `mex`。
### Observations、Editorial 与证明 要让 mex 大于等于 $x$，必须为每个值 $0..x-1$ 选择一名来自不同社团的学生，正是左前缀到社团的完全匹配。若值 `mex` 也能增广，前缀扩大一；第一个不能增广的值就是最大 mex。 逆序加边时匹配不会失效。每次新增学生边后，从当前 mex 尝试增广；成功就继续下一值。记录加回当天学生之前的 mex，正对应当天删除后的状态。成功增广至多 $m$ 次，失败至多 $d$ 次，每次 DFS $O(E)$，本题 $n,m\le5000$ 可接受。 ### 核心伪代码与参考实现附件 ```text potential values are left vertices; clubs are right vertices start with students that never get deleted and maintain a matching advance mex while the current potential can be augmented process deletions in reverse: record current mex for that day add the deleted student's potential-club edge continue augmenting from current mex ``` 完整 GNU C++17 参考实现见附件：[CodeForces-1139E.cpp](../../参考实现/07-二分图/CodeForces-1139E.cpp) ### 复盘与变式 若每天有学生加入，正序即可；若同时删边和加边且不能离线反转，需要动态匹配或分治回滚等更强工具。 ## 扩展与联系 - 最小边覆盖（无孤立点）大小为 $|V|-|M_{max}|$；最大独立集大小为 $|V|-\text{最小点覆盖}$。 - Hall 定理给出左侧全部可匹配的充要条件：任意左点子集的邻居数不少于子集大小。 - 一般图匹配需要 Blossom，Kuhn/Hopcroft–Karp 不能直接使用。 ## 总结与自检 1. 增广路翻转为何保持匹配且大小加一？ 2. Kőnig 定理怎样把网格射击转为匹配数？ 3. mex 至少为 $x$ 为什么是潜力前缀匹配？ 4. 逆序加边时为什么只尝试当前 mex，而不用重算所有更小值？ ## 课后训练建议 先用子集枚举对拍 Kuhn。`Asteroids` 要先写出点覆盖模型再看定理；`Maximize Mex` 先对 3 个社团手推逆序状态，确认记录答案与加回动作的先后。规模扩大后再实现 Hopcroft–Karp 并做同图 A/B。