Kuhn Munkres 算法入门

之前做一道 KM 题，被卡 DFS 了。现在来填坑，学一个 BFS 版。

KM 算法通过维护结点的顶标来求出二分图的最大权完美匹配，其正确性可以由对偶定理证明。

对于$2n$个点左右两边点数相同的二分图$G=(V:(L,R),E)$，KM 算法的复杂度是$O(n^3)$的。

完美匹配：每个点都是某个匹配边的端点的匹配。

最大权匹配转化为最大权完美匹配：对于左右点集大小不相同的二分图，我们可以把点集小的补满，新增一些权值为$0$的边，这不会影响答案。

对于结点$u$，记其顶标为$h_u$，可以理解为点权。记边权为$w$。

KM 算法将在始终保证$h_u + h_v \ge w(u,v)$的情况下最小化$\sum_{u\in L\cup R}h_u$，并给出匹配的方案。根据对偶定理，最小化的$\sum_{u\in L\cup R}h_u$记为最大匹配的权值。

相等子图

KM 算法执行过程中会维护一个子图$G'=(V=(L,R), E'=\{(u,v) \in E| w(u,v) = h_u + h_v\} )$，其中$E'$维护的是满足$h_u + h_v = w(u,v)$的边。

为什么维护相等子图

根据对偶定理，保证$h_u + h_v \ge w(u,v)$的情况下最小化$\sum_{u\in L\cup R}h_u$得到的是最大权匹配。不妨设这个匹配是$P$，那么对于$(u,v) \in P$一定有$h_u + h_v \ge w(u,v)$。两边对$(u,v)\in P$求和，发现是相等的，因此一定有$h_u + h_v = w(u,v)$。

换言之，只要存在$h$使得相等子图有完美匹配，那么我们就找到了最大权匹配。

注意，完美匹配是与权值无关的。这个概念是基于不带权二分图的。在理解 KM 算法的过程中不要与带权匹配混淆。

因此我们有了一个 KM 算法的雏形：

• 在相等子图里増广。
• 如果増广不了，就改一改顶标。

重复上述步骤直到找到完美匹配。当然，因为$|L| = |R|$，所以完美匹配是一定存在的。

KM 算法

直接给出 KM 算法的框架。

初始化：

• 对于$u\in L$，让$h_u = \max_{v\in R} w(u,v)$。
• 对于$u\in R$，让$h_u = 0$。

DFS 版的比较好懂，但是难写而且跑得慢，这里我们讲 BFS 版。

我们依次枚举右部的点$u$来作为増广结束的位置。

然后 BFS：

• 对于右部的点，我们枚举相等子图中与它相邻的点继续搜索；
• 对于左部的点，我们直接跳到与它匹配的点上去。如果没有与它匹配的点，那么我们就找到了増广路。

在 BFS 的过程中记录前驱指针。増广的时候倒着増广。也就是说是从左部的未匹配的点増广到右部的未匹配点（$u$）。

如果増广失败，就考虑调整顶标值。

顶标的调整方式与増广的方向有关。如果是从左到右増广，那么就以左加右减的方式；反之亦然。

左加右减：将左部 BFS 树上的点的顶标统一增加$d$，将右部 BFS 树上的点的顶标统一减少$d$。

设 BFS 树的点集是$T$。

在这样操作之后：

• 相等子图里的边依然满足$h_u + h_v = w(u,v)$。
• 对于$(u,v) : u\in T, v\notin T$的边仍不属于相等子图。
• 对于$(u,v) : u\notin T, v\in T$的边，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。

根本原因

我们的増广路实际上是从 BFS 树的叶子走到根（$u$）。我们应当扩展 BFS 的叶子而不是给 BFS 树的根结点加一个父节点。前者对应$(u,v) : u\notin T, v\in T$的边，后者对应$(u,v) : u\in T, v\notin T$的边。

那么考虑$d$的值。为了保证$h_u + h_v \ge w(u,v)$对每条边成立，则有

$$d = \min_{(u,v) : u\notin T, v\in T} h_u + h_v -w(u,v)$$

实际上我们可以对左部点$u$维护一个松弛变量$\text{slack}(u) = \min_{v\in T} h_u + h_v - w(u,v)$，这样就有$d = \min_{u\notin T}\text{slack}(u)$。而$\text{slack}(u)$可以在 BFS 的过程中维护。

在做完了左加右减之后，至少有一条$(u,v) : u\notin T, v\in T$的边会加入相等子图，即一定会有増广路。因此我们再进行一轮増广即可。

代码