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

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

对于个点左右两边点数相同的二分图,KM 算法的复杂度是的。

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

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

对于结点,记其顶标为,可以理解为点权。记边权为

KM 算法将在始终保证的情况下最小化,并给出匹配的方案。根据对偶定理,最小化的记为最大匹配的权值。

相等子图

KM 算法执行过程中会维护一个子图,其中维护的是满足的边。

为什么维护相等子图

根据对偶定理,保证的情况下最小化得到的是最大权匹配。不妨设这个匹配是,那么对于一定有。两边对求和,发现是相等的,因此一定有

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

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

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

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

重复上述步骤直到找到完美匹配。当然,因为,所以完美匹配是一定存在的。

KM 算法

直接给出 KM 算法的框架。

初始化:

  • 对于,让
  • 对于,让

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

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

然后 BFS:

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

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

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

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

左加右减:将左部 BFS 树上的点的顶标统一增加,将右部 BFS 树上的点的顶标统一减少

设 BFS 树的点集是

在这样操作之后:

  • 相等子图里的边依然满足
  • 对于的边仍不属于相等子图。
  • 对于的边,它原来不属于相等子图,现在可能进入了相等子图,因而使相等子图得到了扩大。
根本原因

我们的増广路实际上是从 BFS 树的叶子走到根()。我们应当扩展 BFS 的叶子而不是给 BFS 树的根结点加一个父节点。前者对应的边,后者对应的边。

那么考虑的值。为了保证对每条边成立,则有

实际上我们可以对左部点维护一个松弛变量,这样就有。而可以在 BFS 的过程中维护。

在做完了左加右减之后,至少有一条的边会加入相等子图,即一定会有増广路。因此我们再进行一轮増广即可。

代码