二分图最大权匹配

二分图的最大权匹配是指二分图中边权和最大的匹配。

Hungarian Algorithm（Kuhn-Munkres Algorithm）

匈牙利算法又称为 KM 算法，可以在 时间内求出二分图的 最大权完美匹配。

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

有了定理 1，我们的目标就是透过不断的调整可行顶标，使得相等子图是完美匹配。

因为两边点数相等，假设点数为 ， 表示左边第 个点的顶标， 表示右边第 个点的顶标， 表示左边第 个点和右边第 个点之间的权重。

首先初始化一组可行顶标，例如

然后选一个未匹配点，如同最大匹配一样求增广路。找到增广路就增广，否则，会得到一个交错树。

令 ， 表示二分图左边右边在交错树中的点，， 表示不在交错树中的点。

在相等子图中：

• 的边不存在，否则交错树会增长。
• 一定是非匹配边，否则他就属于 。

假设给 中的顶标 ，给 中的顶标 ，可以发现

• 边依然存在相等子图中。
• 没变化。
• 中的 有所减少，可能加入相等子图。
• 中的 会增加，所以不可能加入相等子图。

所以这个 值的选择，显然得是 当中最小的边权，

。

当一条新的边 加入相等子图后有两种情况

• 是未匹配点，则找到增广路
• 和 中的点已经匹配

这样至多修改 次顶标后，就可以找到增广路。

每次修改顶标的时候，交错树中的边不会离开相等子图，那么我们直接维护这棵树。

我们对 中的每个点 维护

。

所以可以在 算出顶标修改值

交错树新增一个点进入 的时候需要 更新 。修改顶标需要 给每个 减去 。只要交错树找到一个未匹配点，就找到增广路。

一开始枚举 个点找增广路，为了找增广路需要延伸 次交错树，每次延伸需要 次维护，共 。

Dynamic Hungarian Algorithm

原论文 The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs

伪代码更清晰的论文 A Fast Dynamic Assignment Algorithm for Solving Resource Allocation Problems

相关 OJ 问题 DAP

以下代码应该为论文 2 作者提交的代码（以下代码为最大化权重版本，原始论文中为最小化 cost）

转化为费用流模型

在图中新增一个源点和一个汇点。

从源点向二分图的每个左部点连一条流量为 ，费用为 的边，从二分图的每个右部点向汇点连一条流量为 ，费用为 的边。

接下来对于二分图中每一条连接左部点 和右部点 ，边权为 的边，则连一条从 到 ，流量为 ，费用为 的边。

求这个网络的

最大费用最大流 即可得到答案。

习题