前言

头大~

km算法简介

KM算法全称是Kuhn-Munkras算法，用于解决带权二分图中最大完美匹配的问题

什么是最大完美匹配

对于二分图$G$，其二部划分$(V_1, V_2)$，若所有顶点都是匹配点，则该匹配为完美匹配

什么是增广路

1. 增广路的两端都是未匹配的点
2. 増广路的边按未匹配边-匹配边交替循环
3. 増广路的边数为奇数
4. 还没有想起来的话可以去复习一下匈牙利算法

km算法

km算法通过贪心地向子图中加边并増广达到匹配权值之和最大的目的。

首先，对于二部划分$(x, y)$，定义一个值"标顶"，对于任意边，有$lx_a+ly_b\ge W_{edge}$，初始时有$l_x = max(edge[x][i]), l_y=0$，进而我们可以贪心地构建一副子图$G'(V, E'), E'=\{(x, y)|(x, y) \in E, l_x + l_y = W_{(x,y)} \}$

对$G'$做匹配，当给$x_i$匹配失败时，我们称在左侧($x$集)在増广路上的点集为$L$，右侧同理，称为$R$。此时我们假定一个值$d$，并将増广路左侧($x$集)的标顶减去$d$，増广路右侧($y$集)的标顶加上$d$。那么对于边$(a, b)$

1. 若$a \notin L, b \notin R$，此时$lx_a$与$ly_b$均不变，该边未添加进子图
2. 若$a \in L, b \notin R$，此时$lx_a+ly_b$减小，该边可能添加入子图
3. 若$a \notin L, b\in R$，此时$lx_a+ly_b$增大，该边未添加进子图
4. 若$a \in L, b \in R$，此时$lx_a+ly_b$不变，原本在子图中的边仍保留

这里的$d$取$min(lx_a + ly_b - W_{(a, b)})$，意为要向子图中加边的最小变化值

加边以后，继续按照匈牙利算法的方式増广即可。

参考链接

https://blog.sengxian.com/algorithms/km

https://www.cnblogs.com/wenruo/p/5264235.html

https://www.cnblogs.com/zpfbuaa/p/7218607.html