先来看一个问题：
- 给定 \(w_{1\sim n, 1\sim n}\)，现在要求满足 \(\forall i, j\in [1, n], a_i + b_j\ge w_{i, j}\) 且 \(\sum a_i + \sum b_j\) 最小的 \(a_{1\sim n}, b_{1\sim n}\)。
如果会线性规划对偶，对偶出来后能够发现 \(\sum a_i + \sum b_j\) 就是着左侧 \(n\) 个点右侧 \(n\) 个点，\((i_L, j_R)\) 边权为 \(w_{i, j}\) 的最大权完美匹配（还需要一些调整法辅助），那这之间有什么联系呢？
这就引出了主题——Kuhn–Munkres Algorithm，简称为 KM 算法。
下面指的匹配都默认是完美匹配。
回想二分图匹配问题，一个做法是 Kuhn 算法每次暴力跑出增广路然后反转路径（其实一直被称作匈牙利算法，但是实际上匈牙利算法指的也是 KM 算法）。
为什么这个做法在最大权匹配时用不上了呢？能发现是在二分图匹配时，每个边是平等的，没有优先级顺序，而在最大权匹配时，边权会使得你更想贪心的选一些大的边。
那如果还是想要用上 Kuhn 算法该怎么办呢？
一个想法就是保留下一些边，使得整个图存在完美匹配，且此时每个边平等，跑出来的任意一个匹配都是最大权完美匹配。
此时从边入手就不太可行，于是尝试和点扯上点关系。
不管保留怎样的匹配，其边权和都要相等，这启发对两侧的点构造一个类似势能的值。
在 KM 中，这个值叫作顶标，记 \(xv_i\) 表示左侧 \(i\) 号点的顶标，\(yv_i\) 表示右侧 \(i\) 号点的顶标。
我们可以保留下来 \(xv_i + yv_j = w_{i, j}\) 的边 \((i_L, j_R)\)，那么此时就会发现，任意一个完美匹配的权值都相等，值都为 \(\sum xv_i + \sum yv_j\)。
不过此时还没有保证是最大权匹配啊，什么情况下保留下来的图的匹配不是原图的最大权匹配呢？
对于 \(w_{i, j}\le xv_i + yv_j\) 的边，如果选中了肯定匹配的和不增，所以问题只有可能出现在 \(w_{i, j} > xv_i + yv_j\) 的边 \((i_L, j_R)\) 上，只有选中至少一个这样的边的匹配才有可能比已知匹配的权值大。
于是我们就整理出了两个条件：
- 保留 \(xv_i + yv_j = w_{i, j}\) 的边 \((i_L, j_R)\)，这个图存在完美匹配。
- \(\forall i, j\in [1, n], xv_i + yv_j \ge w_{i, j}\)。
我们声称满足这个条件的 \(\sum xv_i + \sum yv_j\) 一定是相同的，且跑出来的完美匹配就是最大权匹配：
- 保留边后的图存在完美匹配，所以一定存在完美匹配的权值 \(\ge \sum\limits xv_i + \sum\limits yv_j\)，且该完美匹配就是一个取到 \(=\) 的匹配。
- 考虑任意一个完美匹配 \((i_L, p(i)_R)\)（\(p(i)\) 为 \(1\sim n\) 的排列），\(\sum\limits w_{i, p(i)}\le \sum\limits xv_i + \sum\limits yv_j\)。
把 \(\le, \ge\) 叠加，能够知道此时的匹配就是最大权匹配，且 \(\sum xv_i + \sum yv_j\) 的值都为最大权匹配的边权和。
并且能够知道，此时的 \(xv, yv\) 就是满足第二个条件中 \(\sum xv_i + \sum yv_j\) 最小的 \(xv, yv\)。
这是因为对于任意一个满足条件的 \(xv, yv\)，最大权匹配的边权和都应该 \(\le \sum\limits xv_i + \sum\limits yv_j\)，而满足两个条件的 \(xv, yv\) 因为存在完美匹配所以取到了下界，就是最小的 \(xv, yv\) 了。
至此，开头的问题也有了个明确的目标了。
接下来就来考虑求解 KM。
对此，我们考虑使用 Kuhn 中所用的增量法，即每次在已有的相等子图（满足上述 2 条条件的子图）上加入一个还没有配对的左部点，并通过调整顶标找到一条增广路为其匹配一个右端点。
具体来说，首先我们先让整个图初始就满足条件 2。
于是可以初始化 \(xv_i = \operatorname{inf}, yv_j = 0\)。
同时，我们维护已经知道的匹配，用 \(mx_i, my_j\) 表示左右部点各自的匹配点（如果 \(mx_i = j, my_j = i\)，那么有 \(xv_i + yv_j = w_{i, j}\)）。
接下来，考虑从左部点加入一个未匹配的点 \(u\)。
那么我们想要给 \(u\) 找到一个右部点 \(v\)，然后匹配 \(u, v\) 两点。
那如果有 \(v\) 满足 \(xv_u + yv_v = w_{u, v}\)，就可以先选出这个点。
否则就说明 \(\forall v, xv_u + yv_v > w_{u, v}\)，于是我们尝试减小 \(xv_u\)（因为现在不确定右部点的状况，所以不去选择调整右部点），减的值 \(\Delta\) 是多少呢？
首先要存在满足条件的 \(v\)，所以 \(\Delta \ge \min\limits_v (xv_u + yv_v - w_{u, v})\)；其次如果 \(\Delta\) 过大就会违反条件 2，所以 \(\Delta \le \min\limits_v(xv_u + yv_v - w_{u, v})\)。
整理得到 \(\Delta = \min\limits_v (xv_u + yv_v - w_{u, v})\)，\(xv_u\gets xv_u - \Delta\) 后就一定能找到 \(v\) 了。
如果 \(v\) 没有匹配，那直接匹配上 \((u, v)\) 就好了。
但是如果 \(v\) 有匹配，那采用 Kuhn 的算法，考虑 \(u\to v\to my_v\) 的路径，这一条路径是非匹配边和匹配边交错的，这说明如果 \(my_v\) 找到了一个没有匹配的右端点 \(v'\)，可以把 \(u\to v\to my_v\to v'\) 这条增广路的状态反转，即变为 \((u, v), (my_v, v')\) 匹配。
所以当前的目标就是找到一个 \(v'\) 满足 \(xv_u + yv_{v'} = a_{u, v}\) 或 \(xv_{my_v} + yv_{v'} = a_{my_v, v'}\)。
如果找到了自然很好，如果找不到，此时又该怎么调整呢？
此时我们想要保证 \(xv_u + yv_v = w_{u, v}\) 和 \((my_v, v)\) 的匹配关系，又想要加入 \(v'\) 的关系，于是我们考虑这样子调整：让 \(xv_u, xv_{my_v}\) 减 \(\Delta\)，让 \(yv_v\) 加 \(\Delta\)。
那这个 \(\Delta\) 是多少呢？依然用上问的想法可以知道是 \(\Delta = \min\limits_{u'\in \{u, my_v\}, v' = v} (xv_{u'} + yv_{v'} - w_{u', v'})\)。
然后我们会加入 \(v'\)，继续做刚才的操作。
总结一下就是：
- 维护两个集合 \(S, T\) 表示已经被增广的左右部点，令起点为 \(s\)，初始 \(S = \{s\}, T = \varnothing\)。
- 每次令 \(\Delta = \min\limits_{u\in S, v\not\in T} (x_u + y_v - w_{u, v})\)，然后 \(xv_u\gets xv_u - \Delta(u\in S), yv_v\gets yv_v + \Delta(v\in T)\)。
- 此时存在 \(\exist u\in S, v\not\in T, xv_u + yv_v = w_{u, v}\)，便可以把 \(u\to v\) 这条边加入增广路，\(T\gets T\cup \{v\}\)。
- 然后根据 \(v\) 的匹配状况分讨：
- 如果 \(v\) 没有匹配的左端点，那么一定可以找到 \(s\to v\) 的增广路，反转路径状态，结束。
- 如果 \(v\) 有匹配的左端点，那么把 \(v\to my_v\) 加入增广路，\(S\gets S\cup \{my_v\}\)。
如果直接实现，会因为每个 \(s\) 都最多增广 \(n\) 轮，并且找到 \(\Delta\) 是 \(\mathcal{O}(n^2)\) 的复杂度，复杂度将会达到 \(\mathcal{O}(n^4)\)。
不过考虑一个 \(v\not \in T\)，\(\min\limits_{u\in S} (xv_u + yv_v - w_{u, v})\) 的变化：
- 当 \(xv_u\gets xv_u - \Delta(u\in S)\) 时，这个值也会 \(-\Delta\)。
- 当 \(S\gets S\cup \{u'\}\) 时，这个值会与 \(xv_{u'} + yv_v - w_{u', v}\) 取 \(\min\)。
于是可以记下 \(sl_v\) 表示 \(v\) 所需的松弛量（即 \(\min\limits_{u\in S} (xv_u + yv_v - w_{u, v})\) 的值），因为松弛（调整顶标）和加入增广的次数是 \(\mathcal{O}(n)\) 的，复杂度为 \(\mathcal{O}(n^3)\)。
模板题（Luogu P6577 【模板】二分图最大权完美匹配）代码：
#include <bits/stdc++.h>using ll = long long;constexpr ll inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 510;ll w[N][N];ll xv[N], yv[N];
int mx[N], my[N];
int vx[N], vy[N];
std::pair<ll, int> sl[N];int main() {int n, m;scanf("%d%d", &n, &m);memset(w, -0x3f, sizeof(w));for (int x, y; m--; ) {scanf("%d%d", &x, &y);scanf("%lld", &w[x][y]);}memset(xv + 1, 0x3f, sizeof(ll) * n);for (int s = 1; s <= n; s++) {memset(vx + 1, 0, sizeof(int) * n);memset(vy + 1, 0, sizeof(int) * n);vx[s] = 1;for (int v = 1; v <= n; v++) {sl[v] = {xv[s] + yv[v] - w[s][v], s};}auto adds = [&](int u) {vx[u] = 1;for (int v = 1; v <= n; v++) {if (! vy[v]) {sl[v] = std::min(sl[v], {xv[u] + yv[v] - w[u][v], u});}}};auto minsl = [&]() {std::pair<ll, int> mn = {inf * 2, 0};for (int v = 1; v <= n; v++) {if (! vy[v]) {mn = std::min(mn, {sl[v].first, v});}}return mn;};int t;while (true) {auto [d, v] = minsl();for (int i = 1; i <= n; i++) {xv[i] -= d * vx[i];vy[i] ? (yv[i] += d) : (sl[i].first -= d);}vy[v] = 1;if (! my[v]) {t = v;break;} else {adds(my[v]);}}for (int v = t; v; ) {int u = sl[v].second;int v_ = mx[u];mx[u] = v, my[v] = u;v = v_;}}ll ans = 0;for (int i = 1; i <= n; i++) {ans += xv[i] + yv[i];}printf("%lld\n", ans);for (int i = 1; i <= n; i++) {printf("%d ", my[i]);}return 0;
}
后面就是一些无关紧要的问题了。
-
如果说满足条件 1,2，就是满足条件 2 中顶标和最小的一组顶标，那么满足条件 2 且顶标和最小的任意顶标的相等子图是否都存在完美匹配呢？
答案是肯定的，考虑反证，如果不存在完美匹配，考虑对一个没有匹配的左部点 \(s\) 做调整顶标找匹配，能够发现过程中一定有 \(|S| + 1 = |T|\)，这说明每一步调整一定都会使总和 \(- \Delta\)，而因为 \(s\) 没有匹配，所以过程中一定会使总和变小，矛盾。
-
如果边权为 \([-V, V]\)，顶标的值域是多少？
考虑分析最后一个被加入匹配的右部点 \(t\)，那么 \(t\) 一定只会在最后一次增广被增广到，在这之前一直有 \(yv_t = 0\)，又因为 \(\forall u, xv_u + yv_t\ge w_{u, v}\)，也就是 \(\forall u, xv_u\ge w_{u, v}\)。
且最后一次的增量是 \(\Delta = \min\limits_{u\in S} (xv_u + yv_t - w_{u, t}) = \min\limits_{u\in S} (xv_u - w_{u, t})\)，所以对于 \(u\in S\)，\(xv_u - \Delta\ge w_{u, t}\)。
于是可以分析出 \(xv_u\in [-V, V]\)。对于 \(yv_v\)，首先因为 \(\Delta\ge 0\)，所以 \(yv_v\ge 0\)；其次因为至少需要 \(\exist u, xv_u + yv_v = w_{u, v}\)，于是可以得到 \(yv_v\le 2V\)。
于是可以知道 \(yv_v\in [0, 2V]\)。具体的 assert 可以参考这份提交。
需要注意的是，因为不存在的边被设成了 \(-\operatorname{inf}\)，所以 \(V\) 应当为 \(\operatorname{inf}\) 而不是题目中边权的值域。