说个挺常见的现象：网上搜KM算法，十个模板九个是DFS。贴模板的人都说自己复杂度是O(n^3)，但真拉到极限数据上，很多版本会退化。原因不是KM不对，而是写法里藏着反复扫描的额外代价。这篇文章我把能稳定跑出O(n^3)的BFS版本从头到尾拆一遍，包括顶标为什么那样改、slack数组到底省了什么时间、pre数组怎么回溯，最后给一份可以直接抄的C++模板。如果你之前只背过DFS版，看完这篇文章应该能把这块拼图彻底补上。

1. 先用一句话说清KM在解决什么问题

KM算法解决的是二分图最大权完美匹配：左边n个点，右边n个点，两两之间有边权，要找一个一一对应让总权值最大。比如n个工人分配n个任务，效益矩阵已经给好了，目标就是总效益最大。

1.1 问题定义与记号

后面统一用左侧点表示“待匹配的一方”，右侧点表示“被匹配的一方”。边权记作w[i][j]，表示左侧第i个点到右侧第j个点的权值。

• n：左右两侧点数，KM要求两边相等，都是n
• lx[i]：左侧第i个点的顶标
• ly[j]：右侧第j个点的顶标
• matchy[j]：右侧第j个点当前匹配的左侧点，没有匹配时是0
• 交错树：从某个未匹配左点出发，沿着“未匹配边-已匹配边-未匹配边”交替走，能走到的点和边形成的树

KM能处理的前提是“完美匹配一定存在”。如果题目不保证存在，要先把图补成完全二分图，或者先跑一遍匈牙利判断能不能全部匹配，这部分后面第5节会详细讲。

1.2 什么时候该用KM，什么时候别用

KM的优势在稠密图上最明显。当n在几百量级，两两都有边权时，KM的O(n^3)是稳定且容易实现的。如果图很稀疏，只有几条边，那直接费用流或匈牙利相关做法往往更快，因为KM要把缺掉的边补成负无穷，白白多出许多无效计算。

还要注意KM求的是“完美匹配”，也就是每个点都必须匹配到。如果题目只是“左点可以不全部匹配，求最大权匹配”，一种做法是补虚拟点，把不存在的边权补0，让虚拟点去吸收多余容量。这种情况KM仍然能用，但输出方案时要过滤掉虚拟点。

2. 顶标、相等子图与增广思想

KM算法最核心的地方不是“找增广路”，而是“维护一组顶标，慢慢把非相等边变成相等边”。

2.1 可行性顶标与关键定理

给每个点分配一个数，左侧叫lx，右侧叫ly。如果对任意边(i,j)都满足：

lx[i] + ly[j] >= w[i][j]

这组顶标就是可行的。满足lx[i] + ly[j] == w[i][j]的边称为相等边，所有相等边组成的子图叫相等子图。

关键定理一句话就能讲完：如果相等子图里存在完美匹配，那么这个完美匹配就是原图的最大权完美匹配。原因也很简单，任取原图一个完美匹配M，它的总权值一定不超过所有顶标之和：

sum(w[M]) <= sum(lx) + sum(ly)

而相等子图里的完美匹配M*，每条匹配边都取等号，所以：

sum(w[M*]) = sum(lx) + sum(ly)

于是M*就是最优。这个证明和最大权匹配问题里的“对偶变量”是一回事，理解成“把每个点的潜力上限都标出来，能达到上限的边才是好边”就行。

2.2 调整顶标：delta怎么来，怎么改

初始顶标可以这样设置：

• lx[i] = max(w[i][j])，也就是每行最大值
• ly[j] = 0

这样左点的顶标足够大，显然满足lx[i] + ly[j] >= w[i][j]。但初始相等子图往往没有完美匹配，所以需要在找不到增广路时调整顶标。

假设当前交错树已经访问到的左点集合是S，右点集合是T。令：

delta = min( lx[i] + ly[j] - w[i][j] ) , i属于S, j不属于T

然后做如下修改：

• S中所有左点：lx[i] -= delta
• T中所有右点：ly[j] += delta

这样修改后，顶标仍然可行。直观理解是：两个端点都在S和T里的边，一个减delta一个加delta，差值不变；两个端点都不在S和T里的边，两个都不变，差值不变；只有“左点在S、右点不在T”的这条边界边，差值会减少delta。而delta取的是所有这类边里的最小值，所以减少delta后，至少有一条边界边会从“小于等于”变成相等，于是相等子图多一条边，接下来可以继续找增广路。

2.3 从交替树到增广路

每次为一个左侧点找匹配时，本质上是做一次增广。如果右侧点还没匹配，直接配上就行；如果右侧点已经匹配，就去看看它的匹配左点能不能换一条路，找到另一个未匹配右点。

KM里的“换路”比普通匈牙利多了顶标调整这一步。普通匈牙利只需要在相等子图里DFS，而KM在找不到相等边时，通过调整顶标强行多造几条相等边出来，然后继续增广。

这里也顺便说清楚：KM的增广路必须由相等边组成。因为只有相等边才能让匹配权和顶标和相等，这是正确性的基石。

3. 为什么很多DFS写法不是真O(n^3)

网上最常见的KM模板是DFS配合slack数组。我先把这类写法的复杂度问题讲透，因为很多人以为自己写的是O(n^3)，其实不是。

3.1 朴素DFS的复杂度来源

朴素DFS做一次增广时，会从当前左点出发，沿着相等边递归尝试所有可能的路径。一次DFS的最坏情况要遍历整个交错树，而每个左点内部还要枚举所有右点判断lx[i]+ly[j]==w[i][j]，所以一次找增广路的理论开销是O(n^2)。

看起来n个左点，每轮O(n^2)，总复杂度不是O(n^3)吗？问题出在“调整顶标”这一步。

如果每次find失败后，从头再次调用find，那么之前递归过程中访问过的左点可能被重复扫描。交替树可能因为顶标调整而多出新的相等边，递归栈却已经返回了，下一次只能重新从根开始走。最坏情况下，每调整一次顶标就要重新扫描一次，每轮增广可能要调整O(n)次顶标，每次扫描O(n^2)，总复杂度就变成O(n^4)。

3.2 slack数组到底优化了什么

slack数组优化的是“重复计算边界差值”。朴素做法在每次需要求delta时，会把S中所有左点和所有不在T中的右点重新遍历一遍，计算它们之间的最小差值。这个东西如果每次调整顶标都重新算，代价非常大。

用slack[j]记录右侧点j到当前交错树的最小gap：

slack[j] = min( lx[i] + ly[j] - w[i][j] ), i属于S

这样每次扩展交错树时，只需要扫当前左点的邻边更新slack，求delta时直接在所有未访问右点里取min(slack[j])，不用再对S整体遍历。

但注意：slack优化能省掉“重复扫描所有左点”，不能省掉“DFS递归返回后再从头开始”的问题。如果每次更新完顶标后重新调用DFS，那么更新slack时关联到的“新增相等边”到底是从哪个左点连出来的，递归时不一定能重新走到那个左点。很多DFS模板在这里会踩坑。

3.3 递归版容易踩的坑

一个常见DFS写法是这样：find函数里遇到gap大于0就更新slack，gap等于0才访问右点；find失败后，在主循环里修改顶标，然后重新调用find。

问题在于：修改顶标后，新产生相等边的左点可能是之前已经访问过的左点，它的visx标记还在。再次从根调用find时，这个左点不会重新被扫描，于是新增的相等边根本不会被发现。结果就是代码看似在“调整顶标继续找”，实际上可能永远找不到新的可访问右点，或者需要额外遍历所有slack为0的未访问右点来“强行补搜”。

这种补搜逻辑写好了也能过题，但已经接近BFS的思维了，而且细节非常多。与其在递归版本里修来修去，不如直接用BFS把访问顺序控制住。

3.4 用BFS把复杂度钉死在O(n^3)

BFS版的核心思路是：每次扩展交错树时，显式地用循环控制“当前处理哪个左点”，并且每个左点只处理一次。

一轮增广的过程：

• 从根左点u开始
• 当前左点x处理完后，根据slack选一个新的未访问右点y
• 如果y未匹配，增广结束
• 如果y已匹配，就让x = matchy[y]，继续处理x

这样每个左点最多被处理一次，每个右点最多被访问一次。每处理一个左点，枚举所有右点更新slack是O(n)，更新顶标最多也是O(n)。一轮增广最多扩展n个右点，所以一个左点的增广是O(n^2)，n个左点一共O(n^3)。

这才是“真O(n^3)”的原因：它通过BFS顺序保证不会因为递归返回而重复扫描已经访问过的节点。

4. BFS版KM的完整实现与逐段解析

下面给出我实际在用的BFS版KM模板。这份模板用matchy[0]当临时变量，配合pre数组回溯增广路，写法紧凑但每一步都不多余。

4.1 核心数据结构

• w[N][N]：边权矩阵
• lx[N]，ly[N]：左右顶标
• slack[N]：右侧点j到当前交错树的最小gap
• pre[N]：记录右侧点j是从哪个右点转移过来的，用于最后增广
• matchy[N]：右侧点匹配的左侧点
• visy[N]：本轮BFS中右侧点是否被访问

为什么不需要visx？因为每个左点都是由某个已访问右点matchy[yy]带来的，右点访问过一次，它的匹配左点就自然被绑定访问一次。用visy就能确定交错树范围，省掉一整个visx数组。

4.2 bfs(u)过程逐段拆解

void bfs(int u) { int x, y = 0; memset(visy, 0, sizeof(visy)); fill(slack + 1, slack + n + 1, INF); matchy[0] = u; do { x = matchy[y]; visy[y] = true; ll delta = INF; int yy = 0; for (int v = 1; v <= n; v++) { if (visy[v]) continue; ll gap = lx[x] + ly[v] - w[x][v]; if (gap < slack[v]) { slack[v] = gap; pre[v] = y; } if (slack[v] < delta) { delta = slack[v]; yy = v; } } if (delta > 0) { for (int v = 0; v <= n; v++) { if (visy[v]) { ly[v] += delta; lx[matchy[v]] -= delta; } else { slack[v] -= delta; } } } y = yy; } while (matchy[y]); while (y) { matchy[y] = matchy[pre[y]]; y = pre[y]; } }

第一步，matchy[0] = u。这里把0号右点当作虚拟起点，matchy[0]存当前根左点。这样整个BFS循环可以统一写成“从右点y出发，取左点x = matchy[y]”的形式，不需要单独处理根节点。

第二步，枚举所有未访问右点，更新slack。pre[v] = y的意思是：如果v的slack被当前左点x更新成更小值，那么v在增广路径上的前驱右点是y。注意这里存的不是“左点来源”，而是“右点来源”，因为最终回溯时要沿着右点链交换匹配。

第三步，求delta。在所有未访问右点里取slack[v]最小的一个，记为yy。如果delta为0，说明当前就有相等边可以进入交错树，直接跳到第四步；如果delta大于0，则必须调整顶标。

第四步，调整顶标。这一步和DFS版的区别在lx[matchy[v]] -= delta。因为S集合等于所有已访问右点的匹配左点，所以遍历visy中每个右点v，同时更新它匹配的左点，就把S中所有左点都统一减了delta，不会漏掉之前访问过的左点。这也是BFS版能保持“匹配边全在相等子图里”的关键。

第五步，y = yy，进入下一轮循环。如果matchy[y]是0，说明右点y未匹配，增广路找到了，退出循环；否则继续处理新的左点。

第六步，回溯增广：

while (y) { matchy[y] = matchy[pre[y]]; y = pre[y]; }

假设路径是u -> 右a -> 左p -> 右b，pre记录会让pre[b] = a，pre[a] = 0。回溯时先把右b匹配给左p，再把右a匹配给u，完成交换。

4.3 为什么这样更新顶标不会重复减左点

很多人第一次写BFS版时，会习惯性在delta大于0时加上lx[x] -= delta，结果代码一跑就错。原因其实上面已经说了：更新顶标的循环里，v遍历到当前y时，matchy[y] = x，所以当前左点已经被减过delta了。如果再额外减一次，当前左点就会被重复减，破坏顶标可行性，匹配结果也会对不上。

类似地，ly[0]也会被更新，但0号右点只是一个虚拟哨兵，它的顶标不重要。真正重要的是lx[matchy[0]] = lx[u]始终跟着S集合一起变化。

4.4 完整代码模板

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 505; const ll INF = 4e18; int n; ll w[N][N]; ll lx[N], ly[N], slack[N]; int matchy[N], pre[N]; bool visy[N]; void bfs(int u) { int x, y = 0; memset(visy, 0, sizeof(visy)); fill(slack + 1, slack + n + 1, INF); matchy[0] = u; do { x = matchy[y]; visy[y] = true; ll delta = INF; int yy = 0; for (int v = 1; v <= n; v++) { if (visy[v]) continue; ll gap = lx[x] + ly[v] - w[x][v]; if (gap < slack[v]) { slack[v] = gap; pre[v] = y; } if (slack[v] < delta) { delta = slack[v]; yy = v; } } if (delta > 0) { for (int v = 0; v <= n; v++) { if (visy[v]) { ly[v] += delta; lx[matchy[v]] -= delta; } else { slack[v] -= delta; } } } y = yy; } while (matchy[y]); while (y) { matchy[y] = matchy[pre[y]]; y = pre[y]; } } void km() { for (int i = 1; i <= n; i++) { lx[i] = -INF; for (int j = 1; j <= n; j++) { lx[i] = max(lx[i], w[i][j]); } } memset(matchy, 0, sizeof(matchy)); for (int i = 1; i <= n; i++) bfs(i); }

调用km()之前，需要把边权矩阵填好。如果某条边不存在，按题目情况填0或者-INF：

• 求最大权完美匹配且保证有解：不存在的边填-INF
• 求最大权匹配但允许左点剩余：补虚拟点，真实不存在的边填0

4.5 小例子手动验证

用一个2x2的例子验证：

w[1][1] = 10, w[1][2] = 9 w[2][1] = 9, w[2][2] = 1

最优匹配显然是把10和1放一起，或者把9和9放一起，总权18。手动跑BFS版也能得到18，而且最终顶标满足相等子图上的匹配关系。

初始顶标：lx = [10, 9]，ly = [0, 0]。

处理左点1，直接匹配右1。处理左点2时会发现右1已经被占，交错树扩展到左1，然后发现左1到右2的gap是1，调整一次顶标，最终把右1让给左2，右2给左1，得到总权18。

这个例子的意义在于验证：BFS版调整顶标后，新匹配的边确实都在相等子图里。如果更新顶标时漏了之前访问过的左点，最终结果就会不满足这个性质。

5. 常见问题与调试经验速查

下面这些坑我基本都踩过，整理成速查表方便定位。

5.1 结果对不上暴力枚举

写KM最容易出的问题就是“答案看起来差不多，但和暴力差一截”。我建议在小数据上直接随机生成权值，然后暴力枚举所有排列验证。n不超过8时，全排列算一遍很快，能把大部分实现错误暴露出来。

验证时不要把KM结果和某个“感觉上正确的答案”比，要严格比暴力全排列。一旦发现不相等，首选检查点就是顶标更新代码：是不是只减了当前左点，而漏掉了之前的左点。

5.2 权值范围很大时的INF选择

如果边权最大是1e9，n是500，总权值可能到5e11，用long long完全够。但如果题目边权能到1e15，总权值可能溢出，这时INF = 4e18也可能在加法时出问题。稳妥做法是让INF比“所有边权绝对值之和”还大一点，而不是盲目开一个极大的数。

另外，求最大权值时，初始lx[i] = -INF再取max，不能直接设0。如果所有边权都是负数，初始0会让顶标不满足可行性。

5.3 无完美匹配/左右点数不等

KM只保证完美匹配下的最优。如果图不一定有完美匹配，直接跑KM可能返回一个实际上包含不合法边的匹配，而且不会主动报错。

我的处理方式：先跑一遍匈牙利，只看边是否存在，不考虑权值，判断所有左侧点是不是都能匹配到右侧点。如果不能，再决定是补虚拟点还是直接输出无解。

左右点数不等时，通常把少的一侧补几个虚拟点，虚拟点连到另一边所有真实点的边权为0。这样KM跑出的完美匹配里，虚拟点可能匹配到真实点，真实点之间的匹配权值不会被虚拟点污染。

5.4 浮点权值的处理

浮点权值用KM也能做，只要把delta的判断从“等于0”变成“小于eps”。但浮点KM对精度要求高的题目比较麻烦，尤其是w[i][j]和顶标之间做差，可能因为浮点误差导致相等边判断出错。

我的经验是：如果题目权值是整数但输出浮点，优先把权值放大成整数，跑完再除掉；如果必须直接算浮点，就把eps设成1e-9左右，所有比较都用容差。

5.5 调试技巧与自测模板

我会在本地放一个暴力对拍脚本，随机生成n从1到8的完全二分图，权值范围在-10到10之间，然后同时跑KM和全排列暴力，比对结果和匹配方案。每次改完模板，先跑2000组随机数据，全过再提交。

另一个实用技巧是打印最终顶标和匹配边，检查每条匹配边是否满足lx[i] + ly[j] == w[i][j]。如果有一条不满足，说明顶标更新逻辑有问题，而不是数据问题。

最后再分享一个小技巧

如果你是在比赛里快速写KM，我的习惯是把这份BFS模板提前背熟，尤其是lx[matchy[v]] -= delta这一行，每次默写时都要念叨一遍。这个位置是DFS思维最容易顺手写成lx[x] -= delta的地方，一旦写错，小数据可能还碰巧能过，大数据就会挂得莫名其妙。

另外，如果题目给了稠密图但n接近1000，O(n^3)的常数会比较大，BFS版仍然有压力。此时可以优化枚举右点的循环：每轮bfs里只扫有边权的列，或者把矩阵转置一下让访问更连续。多数情况下，500以内的n用这份模板问题不大，超过800就要特别小心常数了。

KM这套顶标思想本身并不难，难的是写法的严谨性。DFS版直观但容易退化，BFS版绕了一点但复杂度可控。如果你之前只在板子上背过DFS，下一次不妨换成BFS版试试，跑几组极限数据就能体会到区别。