二分图最大权匹配（KM）

参考资料

• 二分图最大权匹配（KM） - OI Wiki

简介

KM 算法 求二分图的最大权完美匹配。它给左右部每个点各一个 顶标 $l_x,l_y$，只在满足 $l_x(u)+l_y(v)=w(u,v)$ 的 相等子图 上寻找完美匹配。

当相等子图上找不到增广路时，按当前交错树调整顶标，使更多边进入相等子图，直到匹配完美。朴素实现 $O(n^4)$，用 slack 数组优化后为 $O(n^3)$。

例题

洛谷 P6577 【模板】二分图最大权完美匹配

给定左、右各 $n$ 个点的二分图及若干带权边，求一个权值和最大的完美匹配，并输出该最大权值。