匈牙利算法

别人的博客

设二分图两边的点集分别为 \(X,Y\)，边集为 \(E\)。

基本思想

二分图的匹配 \(M\) 是最大匹配 \(\iff\) 二分图内没有 \(M\) 的增广路径。

证明

见《图论导引》第 85~86 页。

时间复杂度

每次 \(X\) 中选一个顶点 \(x_i\) 作为起点搜索增广路径，搜索需要遍历 \(E\) 内的所有边。因此算法的整体时间复杂度是 \(O(|E|\min(|X|,|Y|))\)，总的来说是一个相当高效的算法。不过有更优的（广度优先策略的阶段化的最大匹配算法 \(O(m\sqrt{n})\) 好像网络流也是这样的）解法，超出了讨论范围。