KM算法学习笔记

Zeven · 2020-07-13 17:53:22 · 个人记录

KM

解决问题：

二分图最大权匹配（可以限定匹配次数），复杂度O(n^3)

适用条件：

图存在完备匹配。如果不存在的话可以通过添加虚点虚边来解决问题。

定义：

相等边：满足lx[x]+ly[y] = e(x,y)的边。

相等子图：相等边及对应点构成的子图。

交替树：一次寻找增广路中，访问到的所有点构成的树型结构。

引理：

相等子图有完备匹配的时候原图恰有最大权匹配。

证明：选择的边一定是相等子图内的边，否则e(x,y)<lx[x]+ly[y]，不是最优。

思路：

贪心、增量修改扩张子图

朴素实现O(n^4)：

三种边：相等边、匹配边、其他边

一开始把标号设为INF，再不断缩小来扩张相等子图，直到最后形成完备匹配。

每次从当前点出发寻找以其作为起点，走相等边的增广路，访问到的点构成交替树。

如果没有增广路的话：

然后把交替树左部的点-=d，右边的点+=d。

d为由交替树左部点x出发，y右部点不在交替树内的其他边中delta最小的一条e(x,y)。

然后不断进行该过程。

证明：

分类讨论计算影响：

A/B都在树内或者树外，无影响。

A在树内，B在树外：由于已经增广完毕，所以不存在相等边和匹配边，故会使其他边减小，且至少会使一个降为0并使一个新的B加入交替树内，满足需求。

A在树外，B在树内：

1、匹配边：不存在（因为B集合的匹配点都会在增广路的时候进行扩展）

2、相等边（障碍之处）

即存在左部点在树外，右部点在树内的情况下，修改会使一条相等边变成其他边。

这条边不是匹配边，修改其不会减少匹配次数，我们只需要保证在不断修改下最终得到一条增广路即可（这就要求需要保证有完备匹配），所以我们可以暂且让它变大。

3、其他边：同上

复杂度：

这样的话对于每一个点的修改次数是O(n)级别的，因为最多修改O(n)次所有右部点都会进入交替树，必然出现新的增广路。总复杂度O(n^4)

O(n^3)

通过每次求增广路的时候记录重复信息来节省时间复杂度。

1、把所有没有匹配的左部点加入访问集合并更新sl[y]，sl[y]表示右部在y的其他边的最小delta（同时记录前驱）。

2、执行修正操作（注意需要同时修改sl[y])。

3、如果sl[y]=0的话，则可以由其开始进行增广操作。

如果其没有匹配过的话就形成一组解；否则的话把其放入交替树内并更新，回到1。

这样一次访问全图可以得到一条增广路，复杂度O(n^3)

特殊性质

KM算法，如果把lx设为INF的话，前i次结果恰为选择i次的结果。

证明：此过程相当于找最长路。

考虑d的贡献：x子树内-=d,y子树内+=d，不断重复发现我们最后匹配了一组(x,y)，则：每次我们将所有没有匹配的x都放进交替树，并将其lx[x]减少d，而y每次加入交替树就可以有一组匹配，ly[y]一定是0。

故匹配结果为：lx'[x]+ly'[y]=lx[x]-\sum d.

我们每次选择最小的一个d等价于寻找一个最长的增广路，故证明成立。

KM算法与费用流