从二分图到网络流

二分图最大权匹配

二分图匹配，但是每条边有一个边权，求一个匹配使得边权和最大。

如果不用网络流，可以用 KM 算法。

考虑到二分图中两个集合中的点并不总是相同，为了能应用 KM 算法解决二分图的最大权匹配，需要先作如下处理：将两个集合中点数比较少的补点，使得两边点数相同，再将不存在的边权重设为 $0$，这种情况下，问题就转换成求 最大权完美匹配问题，从而能应用 KM 算法求解。

算法流程

首先我们给每个顶点赋一个可行顶标，其中左边标记为 $lx_i$，右边标记为 $ly_i$，使得对所有边 ($u$,$v$) 满足 $w_{u,v}\leq lx_u+ly_v$。

那么，考虑这个图 G 的一个子图 G'，使得 G' 包含 G 中所有点，但只有那些满足 $w_{u,v}=lx_u+ly_v$的边。那么，对 G' 的一个完美匹配，它的权值就等于$\Sigma_{i=1}^{n}lx_i+ly_i$。也就是说我们需要最大化这个和。

将 $lx_i$ 初始赋值为 $max_{j=1}^{n}w_{i,j}$，$ly_i$ 初始赋值为 $0$，然后选一个未匹配点，如同最大匹配一样求增广路。找到增广路就增广，否则，我们可以尝试调整顶标。

调整顶标过程中，其实就是要不断的加入新的边，也就是使更多的边满足 $lx_i+ly_j=w_{i,j}$ 。那么接下来找一条边 ($i$，$j$) ，使其满足 $i$ 不在二分图最大匹配中，而 $j$ 在二分图最大匹配中。我们希望这条边加入二分图匹配，就要使这条边满足条件，即顶标和要减少 $d=lx_i+ly_j−w_{i,j}$ 。 因为此时点 $j$ 在二分图最大匹配中，如果改变顶标会影响其他边，所以可以对于在二分图最大匹配中的任意点 $i$ ，将 $lx_i+d$ 或 $ly_i−d$ 。为了防止修改完导致部分顶标不满足 $lx_x+ly_y≥w_{x,y}$ ，每次找的 $d$ 要尽量小。 每次找边复杂度 $O(n^2)$，二分图最大匹配的复杂度 $O(n^2)$，总复杂度 $O(n^4)$。