KM 算法解析：带权二分图最优匹配与顶标调整

引言

在信奥新赛季的图论备考中，二分图匹配是一个绕不开的高频考点。前面我们聊过「二分图最大匹配」（匈牙利算法）求的是匹配边数最多；而真实竞赛里更常见的是——每对配对都有一个权重，要求选出的配对总权重最大。比如科技节上让同学和展位一一搭档，谁和哪个项目配合最默契，就是典型的「带权二分图最优匹配」问题。

解决它的算法叫 KM 算法（Kuhn–Munkres，也称匈牙利算法的带权版本），可以在 O(n³) 时间内求出最大权完美匹配。本文用一个原创实例，带你吃透顶标、相等子图、交错树与顶标调整这四块核心，并给出 C++ / Python 双版实现。

题目 / 项目目标

【原创题】校园科技节最佳搭档配对

有 n 名同学（左部集合 X）与 n 个展示项目（右部集合 Y），必须为每个同学分配且只分配一个项目，每个项目也恰好由一个同学负责。已知同学 i 对项目 j 的「适配默契度」为 w[i][j]（可为负）。请设计一种一一配对方案，使所有配对的默契度之和最大。

以 n = 4 为例，默契度矩阵如下（行是同学，列是项目）：

最优配对为：同学2→项目0(4)、同学0→项目1(5)、同学3→项目2(7)、同学1→项目3(7)，总默契度 23。下面解释算法如何自动算出这个结果。

核心考点

解法 / 拆解

算法主流程为「为每个左部点依次找增广路」：初始顶标可行 → 在相等子图中 DFS 找增广 → 找到就匹配、处理下一个点；找不到就调整顶标，直到该点也能匹配。每个左部点最多触发 O(n) 次顶标调整，每次调整 O(n)，DFS 本身 O(n)，整体 O(n³)。

C++ 实现

#include <bits/stdc++.h>
using namespace std;

const int N = 310;
const int INF = 1e9;
int n;
int w[N][N];
int lx[N], ly[N];
int match[N]; // match[y] = x（右部点 y 匹配到的左部点）
bool visx[N], visy[N];
int slack[N];

// 为左部点 x 在相等子图中寻找增广路
bool dfs(int x) {
visx[x] = true;
for (int y = 0; y < n; y++) {
if (visy[y]) continue; // 右部点已在交错树中，跳过
int gap = lx[x] + ly[y] – w[x][y]; // 与相等子图的距离
if (gap == 0) { // 相等边：可走
visy[y] = true;
if (match[y] == -1 || dfs(match[y])) {
match[y] = x;
return true;
}
} else { // 记录松弛量
slack[y] = min(slack[y], gap);
}
}
return false;
}

int km() {
memset(match, -1, sizeof(match));
for (int i = 0; i < n; i++) {
lx[i] = *max_element(w[i], w[i] + n); // 左部顶标取行最大值
ly[i] = 0; // 右部顶标初始为 0
}
for (int cx = 0; cx < n; cx++) { // 依次为每个左部点找匹配
fill(slack, slack + n, INF);
while (true) {
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (dfs(cx)) break; // 找到增广路，匹配成功
int d = INF; // 最小可改进量
for (int y = 0; y < n; y++)
if (!visy[y]) d = min(d, slack[y]);
// 调整顶标：交错树内左部 -d，右部 +d
for (int x = 0; x < n; x++)
if (visx[x]) lx[x] -= d;
for (int y = 0; y < n; y++) {
if (visy[y]) ly[y] += d;
else slack[y] -= d;
}
}
}
int sum = 0;
for (int y = 0; y < n; y++)
if (match[y] != -1) sum += w[match[y]][y];
return sum;
}

int main() {
n = 4;
int ex[4][4] = {
{3,5,4,2},
{6,2,8,7},
{4,3,5,1},
{2,6,7,4}
};
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
w[i][j] = ex[i][j];
cout << km() << endl; // 输出 23
return 0;
}

Python 实现

def km_max(w, n):
INF = float('inf')
lx = [max(row) for row in w] # 左部顶标：每行最大值
ly = [0] * n # 右部顶标
match = [-1] * n # match[y] = x

for cx in range(n): # 依次为每个左部点找增广路
slack = [INF] * n
while True:
visx = [False] * n
visy = [False] * n

def dfs(x):
visx[x] = True
for y in range(n):
if visy[y]:
continue
gap = lx[x] + ly[y] – w[x][y]
if gap == 0: # 相等边
visy[y] = True
if match[y] == -1 or dfs(match[y]):
match[y] = x
return True
else:
slack[y] = min(slack[y], gap)
return False

if dfs(cx):
break
d = min(slack[y] for y in range(n) if not visy[y])
for x in range(n):
if visx[x]:
lx[x] -= d
for y in range(n):
if visy[y]:
ly[y] += d
else:
slack[y] -= d

return sum(w[match[y]][y] for y in range(n))

# 示例
w = [
[3, 5, 4, 2],
[6, 2, 8, 7],
[4, 3, 5, 1],
[2, 6, 7, 4],
]
print(km_max(w, 4)) # 输出 23

跑上面的例子，两种语言都输出 23，与手算的最优方案一致：同学2→项目0、同学0→项目1、同学3→项目2、同学1→项目3。

时间 / 空间复杂度

• 时间复杂度：O(n³)。外层为 n 个左部点，每个点最多 O(n) 次顶标调整，每次调整与 DFS 均为 O(n)。
• 空间复杂度：O(n²)，主要来自权重矩阵 w[n][n] 与若干长度为 n 的辅助数组（顶标、标记、slack）。

易错点

进阶

• 最小权匹配：把所有边权取相反数跑最大权 KM，结果再取反即可。
• 非方阵 / 最大权匹配（不一定完备）：把缺失的边权补 0 后求完美匹配；若只求「边数最多且权最大」，可补足够小的负权虚拟边。
• 与费用流的关系：带权二分图最大权匹配等价于二分图最小费用最大流（边权取负），KM 是专门针对「完美匹配」这一特殊结构的 O(n³) 高效算法；规模很大或带容量限制时改用费用流更通用。
• 匈牙利算法是 KM 的特例：把所有边权都视为 1，KM 退化为普通二分图最大匹配。
• 经典模板题：洛谷 P6577【模板】二分图最大权完美匹配，可拿来练手验证自己的板子。

小结与互动

KM 算法的灵魂在于「用顶标把难解的最大权匹配，缩到相等子图里用熟悉的增广路去解」。记住三步曲：顶标初始化 → 相等子图找增广 → 找不到就调顶标，再配合 slack 把复杂度压到 O(n³)，这道题就稳了。

👉 你第一次学 KM 时，最容易卡在哪一步？是顶标调整的方向，还是相等子图的定理证明？欢迎在评论区聊聊，也欢迎把这篇分享给正在备赛的同学～

📚 免费少儿编程资料（夸克网盘领取）

以下资料来自夸克网盘分享，点击链接可直接保存；若需在 App 内打开，也可复制下方明文链接：

资料持续更新，关注获取最新分享。