KM 算法
概念推导
- 可行顶标：每个节点有一个顶标值 $L(u)$，二分图两边的顶标分别记为 $Lx(u),Ly(v)$
- 可行顶标性质：$lx(x)+ly(y)\geq w(x,y)$
- 可行边：边 $w(x,y)$ 满足 $lx(x)+ly(y)=w(x,y)$
- 相等子图：原图中只包含可行边的生成子图
- 完备匹配：匹配中每个顶点与某条边相关
- 最大权重匹配定理：若某个相等子图中有完备匹配，则该匹配为原图最佳匹配
- 松弛函数：二分图一边的节点保存 $slack(x)=\min(lx(i)+ly(j)-w(i,j))$
- 顶标修改：减少不在交错路中最小的松弛值
算法流程
- 初始化可行顶标值
- 用匈牙利算法寻找相等子图的完备匹配
- 无增广路则修改顶标
- 重复2,3至找到完备匹配