KM · 顶标与相等子图

带权二分匹配：Kuhn–Munkres

二分图最大匹配只问一件事：最多能配成几对。现实里的配对多半还带一个数，某人做某事的熟练度、某条航线的收益、某台机器跑某道工序的耗时。目标于是从「配得多」变成「配得最划算」： $n$ 个人、 $n$ 项任务、一张 $n \times n$ 的权矩阵，求一个完美匹配让总权最大。

本页讲它的经典解法 Kuhn–Munkres，再把同一个实例交给最小费用流跑一遍。两条路给出同一个最优值，差别在别的地方。

1 · 最大权完美匹配

定义 1.1（assignment problem） 给定 $n \times n$ 的权矩阵 $w$ ， $w(i,j)$ 为第 $i$ 个人做第 $j$ 项任务的收益。求一个双射 $\sigma$ ，使 $\sum_i w(i, \sigma(i))$ 最大。

人与任务一样多、任意一对都允许配上，所以完美匹配一定存在。可行性不成问题，难的是从 $n!$ 种配法里挑出总权最大的那一个。这与本系列前几页的困难恰好相反：max-flow 与 residual network 那条线上，能不能送到是主要矛盾；到了带权匹配，能配是给定的，怎么配才是问题。

最省事的做法是每人各挑自己评分最高的任务，但这套贪心两头不讨好。三个人的最高分若落在同一项任务上，第一步就撞车；即使不撞车，让评分最高的人退让一步、把任务腾给只擅长这一项的人，总权也可能更高。逐行的局部最优与全局最优没有关系。

2 · 顶标与相等子图

Kuhn–Munkres 不在权矩阵上直接搜索，而是先给每个点挂一个数，把「最优」翻译成「取等」。

定义 2.1（vertex labeling） 一组实数 $l(x_i)$ 与 $l(y_j)$ 称为可行的 vertex labeling，若对所有 $i, j$ 都有 $l(x_i) + l(y_j) \ge w(i,j)$ 。其中取等的那些边张成的子图称为 equality subgraph。

初值取 $l(x_i) = \max_j w(i,j)$ 与 $l(y_j) = 0$ ，可行性直接成立，此时 equality subgraph 恰是每行最大值所在的那几条边。这也解释了为什么贪心是 KM 的第 0 步：它给出的正是初始 equality subgraph 上的一个匹配。

定理 2.2 设 $l$ 可行。若 equality subgraph 上存在完美匹配 $M$ ，则 $M$ 是权最大的完美匹配，且 $w(M) = \sum_i l(x_i) + \sum_j l(y_j)$ 。

证明任取一个完美匹配 $N$ 。它的每条边 $(i,j)$ 满足 $w(i,j) \le l(x_i) + l(y_j)$ ，而 $N$ 把每个 $x_i$ 与每个 $y_j$ 各用一次，逐边求和得 $w(N) \le \sum_i l(x_i) + \sum_j l(y_j)$ 。这个上界对任何可行的 $l$ 都成立。 $M$ 落在 equality subgraph 里，它的每条边都取等，同样求和即得 $w(M)$ 等于该上界。故 $w(N) \le w(M)$ 。∎

顶标之和因此是一个随时可算的上界，算法要做的只是把它压到某个完美匹配够得着为止。压的手段不是改匹配，而是改顶标：equality subgraph 是顶标的函数，顶标一动，可用的边集就跟着动。

3 · 增广失败时的顶标调整

算法在 equality subgraph 上跑无权版本的 Kuhn 增广：每次固定一个未配对的左点作根，沿取等的边前进，走到未配对的右点就翻转整条交替路，匹配数加一。麻烦在于 equality subgraph 的边通常很少，搜索常常半途走不动。

定义 3.1（alternating tree 与 slack） 搜索过程中与根同奇偶的左点构成 $S$ ，已被访问的右点构成 $T$ ，两者合成一棵 alternating tree。对 $T$ 之外的右点 $j$ ，记 $\mathrm{slack}(j) = \min_{i \in S} \big(l(x_i) + l(y_j) - w(i,j)\big)$ ，即这一列离进入 equality subgraph 还差多少。

走不动意味着 $S$ 在 equality subgraph 里的邻居全落在 $T$ 内。此时取 $\delta$ 为 $T$ 之外各列 slack 的最小值，把 $S$ 里的左顶标各降 $\delta$ 、 $T$ 里的右顶标各升 $\delta$ 。三件事同时成立：

可行性不破。两端为 $i \in S$ 与 $j \notin T$ 的边正好降 $\delta$ ，而 $\delta$ 取的就是这批边里最小的 slack，降完仍不越界；两端为 $i \notin S$ 与 $j \in T$ 的边反而升 $\delta$ ，更宽松；其余两类边一降一升相互抵消或原样不动。
已经长出来的树全部保留。树上的边两端要么同属 $S$ 与 $T$ ，一降一升抵消；要么两端都在树外，不动。搜索接着上一步往下走，不必从头再来。
至少一条新边进入 equality subgraph，即取到最小值的那一列，它的 slack 归零。

顶标之和降 $\delta \cdot (|S| - |T|)$ ，而 alternating tree 上恒有 $|S| = |T| + 1$ ，所以每次调整把 §2 那个上界正好压低 $\delta$ 。上界严格下降、匹配数只增不减，两者夹逼，算法必然终止。

三个人的最高分全落在同一列的那个实例里，有一次调整发生在 $T$ 还是空集时： $S$ 只有根一个点，右顶标一个都不动，效果只是把根的顶标从 9 降到 8，压到它本行的次大值上。写这一页时先按 $|S| \ge 2$ 的一般情形理解这一步，读实测帧才注意到 $T$ 为空这种退化形态，它看起来不像调整，更像补上初值多给的余量。

图 3-1 · KM 在权重表上的单步执行。格内小字是归约量

l(x_i) + l(y_j) - w(i,j)

，为 0 即在 equality subgraph 里；可切换实例，对照调整顶标那一帧新入相等子图的边。

4 · 费用网络上的同一问题

带权匹配也可以不动脑筋地交给费用流。建网与二分图最大匹配的单位容量网完全一样，只给中间那层边多加一个 cost。为把「总权最大」翻成「总费用最小」，取常数 $C$ 不小于全表最大权，令 $\mathrm{cost}(i,j) = C - w(i,j)$ ，费用随之非负，SSP 对权的要求得以满足。完美匹配用满 $n$ 条中间边，总费用等于 $nC$ 减去总权，最小化前者即最大化后者。

图 4-1 · 同一实例建成费用网后的逐次增广，每步推 1 单位流。底部并排列出两种解法各自落到的匹配与总权。

排班那个实例上，两种解法给出的并不是同一个匹配：KM 落在 p1-t2 p2-t1 p3-t3 p4-t4，SSP 落在 p1-t1 p2-t3 p3-t2 p4-t4，总权同为 31。原本以为两条路会收敛到同一个解，跑完才发现这张权矩阵有并列最优；assignment.test.ts 把两组配对都写死了，免得日后改动引擎时把其中一个当成回归。

两者的取舍不在快慢的量级上，而在能表达什么。KM 只解 $n \times n$ 的完美匹配，一次调整就把整棵树往前推，稠密图上是 $O(n^3)$ 且常数很小。SSP 每轮要跑一次容许负权的最短路，朴素实现是 $O(n \cdot VE)$ ，配上 Johnson 势函数后降到 $O(n \cdot E \log V)$ 量级。矩阵稠密、规模不大、形态就是标准 assignment problem 时选 KM；一旦出现「一个人能接两件事」「某几对不许配」「还要顺带满足下界」这类附加条件，费用流改几条边的容量就是新问题，KM 则要重写。

警示 · 最大与最小、以及不许配的对。文献里的 Kuhn–Munkres 多写成求最小代价，本页求最大权；两者只差一次取负或本节那个 $C - w$ 平移，但顶标初值与不等号方向要跟着翻，照抄另一种写法的伪代码是常见的出错点。另外，若某几对不许配，不能把它们的权设成 0，那等于允许它们以零收益配上；应设成足够小的负数，或者干脆用费用流，不许配的边根本不建。

5 · 参考文献

Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2), 83–97.
Munkres, J. (1957). Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics, 5(1), 32–38.
Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2), 248–264.