02-最大匹配Konig与增量Mex.md 7.9 KB
二分图最大匹配：增广路、Kőnig 定理与增量维护
本节目标
学完后，你应能从“左右对象一一配对”建二分图，证明增广路算法，使用 Kőnig 定理把最小点覆盖转成最大匹配，并在只增边的过程中复用已有匹配维护最大可行前缀。
前置知识与课前自测
前置：二分染色、DFS、集合覆盖。
- 当前匹配不是最大时，必然存在什么结构？
- 一条增广路翻转匹配/非匹配边后，匹配大小改变多少？
- 二分图最小点覆盖大小与最大匹配大小有什么关系？一般图也成立吗？
自测答案
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
- 原来源：USACO
- 大致难度：匹配模型建立；考点：Kuhn 增广路
多组数据，至多 200 头牛和 200 个牛栏。每头牛给出愿意进入的牛栏，每牛、每栏至多匹配一次，求最大分配数。
Hint 1
牛为左点，牛栏为右点，意愿为边。Hint 2
对每头牛寻找一条增广路；遇到已占牛栏时，递归尝试迁走原牛。Editorial 与证明
逐个左点做 DFS 增广。若找到空右点或能递归为原匹配左点找到替代，就把当前左点配到该右点。每次成功匹配数加一；当所有未匹配左点都无增广路时，由 Berge 引理当前匹配最大。规模 200，$O(NE)$ 足够。
核心伪代码与参考实现附件
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
复盘与变式
若每头牛和牛栏有配对收益且要求总收益最大，变成带权二分匹配；单纯优先选收益最大边不正确。
精选例题 2：Asteroids
来源信息与题意
- VJudge：POJ-3041 Asteroids
- 原来源：USACO 2005 November Gold
- 大致难度：提高；考点：最小点覆盖 = 最大匹配
$N\le500$ 的网格有 $K\le10^4$ 个小行星。一次射击可清除整行或整列，求清除全部小行星的最少射击数。
Hint 1
把每一行视为左点、每一列视为右点；小行星是连接其行列的边。Hint 2
选择一行/列开火，就是选择一个端点覆盖关联边；目标是最小点覆盖。Hint 3
二分图 Kőnig 定理把答案变成最大匹配大小。Observations、Editorial 与证明
每颗小行星对应行—列边，开火集合必须覆盖所有边，反之任一点覆盖给出清除方案。因此答案是最小点覆盖大小；Kőnig 定理说明它等于最大匹配。用 Kuhn 求匹配，复杂度 $O(NE)$，这里至多约五百万级有效扫描。
核心伪代码与参考实现附件
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
复盘与变式
若行列射击费用不同，变成二分图最小权点覆盖，可用最小割；Kőnig 的“只比较数量”不再直接给答案。
精选例题 3：Maximize Mex
来源信息与题意
- VJudge：CodeForces-1139E Maximize Mex
- 原题：Codeforces Round 548 (Div. 2)
- 难度：2400；考点：mex 前缀匹配、逆序加边、增量增广
$n\le5000$ 名学生属于 $m\le n$ 个社团，每人有潜力 $p_i<5000$。每天一人永久退社；退社后从每个社团至多选一人，最大化所选潜力多重集的 mex。输出每天删除后的最大 mex。
Hint 1
mex 至少为 $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$ 可接受。
核心伪代码与参考实现附件
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
复盘与变式
若每天有学生加入，正序即可；若同时删边和加边且不能离线反转，需要动态匹配或分治回滚等更强工具。
扩展与联系
- 最小边覆盖（无孤立点）大小为 $|V|-|M_{max}|$；最大独立集大小为 $|V|-\text{最小点覆盖}$。
- Hall 定理给出左侧全部可匹配的充要条件：任意左点子集的邻居数不少于子集大小。
- 一般图匹配需要 Blossom，Kuhn/Hopcroft–Karp 不能直接使用。
总结与自检
- 增广路翻转为何保持匹配且大小加一？
- Kőnig 定理怎样把网格射击转为匹配数？
- mex 至少为 $x$ 为什么是潜力前缀匹配？
- 逆序加边时为什么只尝试当前 mex，而不用重算所有更小值？
课后训练建议
先用子集枚举对拍 Kuhn。Asteroids 要先写出点覆盖模型再看定理；Maximize Mex 先对 3 个社团手推逆序状态，确认记录答案与加回动作的先后。规模扩大后再实现 Hopcroft–Karp 并做同图 A/B。