二分图匹配 简要总结

内容主要总结自 OI Wiki。

---

概念

• 二分图：可以划分为两个内部无边点集的图
• 匹配：没有公共点的边集
• 极大匹配：无法继续增加边的匹配
• 最大（权）匹配：边数（边权和）最大的匹配
• 完美匹配：所有点都有邻接边属于匹配
• 交错路：由匹配边与非匹配边交错而成的路径
• 增广路：始于非匹配点且终于非匹配点的交错路

算法

最大流算法

二分图最大权匹配问题可以建模为最大费用最大流问题：两部分别与源点、汇点间连流量为 1，费用为 0 的边，两部间连流量为 1，费用为边权的边；另外由于最大权匹配不一定是最大匹配，还要在左部和汇点间连流量为 1，费用为 0 的边。此时最大流一定为左部点数，最大费用即最大权。

最大费用最大流问题使用 SSP 或原始对偶等算法解决，此处略。

如果是无权的最大匹配问题，可以直接建模为最大流问题，此处略。

增广路算法

匈牙利算法是一种用于解决二分图最大匹配问题的 $O(nm)$ 算法。主要思路是枚举未匹配点找增广路。具体做法为：枚举所有点，进行 DFS 找第一个未匹配点，若找到除自身外的未匹配点，则相当于找到一条增广路，此时更新路上的匹配关系，匹配大小加一。每个点只需要枚举一次，证略。

KM 算法是一种用于解决二分图最大权完美匹配问题的算法。对于普通的二分图最大权匹配问题，可以进行补点使得两部分大小相同，然后利用 KM 算法解决。KM 算法原理略。

---