KM 算法

· · 个人记录

KM 算法解决的是二分图带权最大完美匹配问题。

权均为一的时候，贪心地尽量匹配是最优的，因为只要匹配了，带来的收益都一样。但如果权不同，就无法简单贪心了。

我们引入顶标的概念。每个点有一个顶标，记为 d_x。一组可行顶标，需要满足 d_x + d_y \ge w_{xy}。我们再定义，一个顶标生成一张相等子图，其中包含所有点，以及满足 d_x + d_y = w_{xy} 的所有边。

顶标有什么用？有一个性质，即：如果一组可行顶标生成的相等子图中有一个完美匹配，那么这就是原图的最大权完美匹配。

这是因为相等子图中的边都是使得 d_x + d_y = w_{xy} 的，而原图的边是 d_x + d_y \ge w_{xy}。只要相等子图中有完美匹配，其权一定是最大的。

那么，我们现在的问题就是，选择一组合适的可行顶标，使得其生成的相等子图中有最大匹配。我们不妨先构造任意的顶标，随后调整它。

先让最开始每个右部点的顶标为零，每个左部点的顶标，为它所连的边的最大权。这样，最开始的相等子图就是最大权的那些边。在这张相等子图中跑匈牙利算法，看可否得到完美匹配。

如果得不到，我们就要调整顶标。可以将左部点顶标增加 d = \min \{d_x + d_y - w_{xy}, d_x + d_y \gt w_{xy}\}，右部点减少这个量。这样，我们保证了增加至少一条边，同时原来的边保存，而且增量也尽可能小。然后我们重复跑最大匹配，直到找到完美匹配。

这个复杂度最差是 O(n^4)。考虑优化。我们发现，每次加边时，原来的交错树依旧可用。可以改用 BFS，每次扩展新点时候只是入队，不从头增广。复杂度是 O(n^3)。