《算法的乐趣》第二十一节

本节先总结了匈牙利算法的实现要点：以顶点集合为基础，从X集合逐个选点用DFS或BFS搜索增广路径，单次搜索耗时O(E)，整体复杂度O(V*E)……

本节先总结了匈牙利算法的实现要点：以顶点集合为基础，从X集合逐个选点用DFS或BFS搜索增广路径，单次搜索耗时O(E)，整体复杂度O(V*E)；并提到一次找多条不相交增广路径的Hopcroft-Karp算法，复杂度可达O(sqrt(V)*E)。

随后引入带权匹配：给每个配对指定权重，求边权之和最大的匹配。带权匹配与完美匹配、最大匹配没有包含关系，只有当最大权匹配恰好是完美匹配时才称最佳匹配，这要求数据本身存在完美匹配。

Kuhn-Munkres算法（KM算法）为每个顶点设顶标A[i]、B[i]，若所有满足A[i]+B[j]等于边权的边构成的相等子图存在完美匹配，该匹配即最大权匹配。流程为：初始化顶标（A[i]取相邻最大边权），在相等子图中用匈牙利算法找完美匹配；若失败，则按增广路径上的S、T集合计算变化量dx，S中顶标减dx、T中顶标加dx，使更多边进入相等子图，反复调整直至找到完美匹配。最后以5名工人完成5种工作的经济效益矩阵为例给出实现。