先聊一个很多人踩过的认知坑：KM算法到底是O(n^3)还是O(n^4)。我在网上看过无数模板和题解，有的直接甩一个递归DFS写法说“这就是O(n^3)”，结果遇到构造数据跑得比O(n^4)还难看；有的用slack数组优化了找delta的过程，但主循环里每次失败都从头清空vis重新DFS，最坏还是没有降到严格O(n^3)。这个话题就是围绕“带权二分图最大权完美匹配”里KM算法的严格O(n^3)实现展开的。如果你刷过带权匹配题目，或者在你的某个项目里做过任务分配、多目标匹配这类事，一定知道复杂度被坑的痛。这篇文章会把KM的原理、slack数组到底优化了什么、为什么DFS版容易写“假O(n^3)”、以及真正严格的BFS版写法全部讲透，最后附上我自己的调试经验。

1. 先弄清KM在算什么：顶标、相等子图与复杂度痛点

1.1 KM算法解决的是哪种问题

KM算法解决的是带权二分图最大权完美匹配问题。通俗说，左右各有n个点，每个左侧点和每个右侧点之间都可能有一条带权边，要求选出n条边，使得每个左侧点恰好匹配一个右侧点、每个右侧点也恰好匹配一个左侧点，并且选出的这n条边权值之和最大。

最典型的场景就是任务分配：n个工人、n个任务，第i个工人做第j个任务能产生w[i][j]的效益，要求每人分配一个任务且每个任务只能分给一个人，求最大总效益。这个模型在项目管理、资源调度、多传感器目标关联、图像特征点匹配等实际领域都会出现。

无权二分图求最大匹配通常用匈牙利算法，但匈牙利算法只关心“匹配了多少条边”，不关心边的权重。KM算法可以看作匈牙利算法在带权图上的扩展：它不是在原图上直接找增广路，而是维护一组顶标，通过构造“相等子图”来逐步扩大可匹配边集合，最终在相等子图上找到完美匹配。

1.2 可行顶点标号和相等子图

为每个左侧点设置一个顶标lx[i]，为每个右侧点设置一个顶标ly[j]。要求满足： lx[i] + ly[j] >= w[i][j]

这是一条硬性条件。只要时刻保证这个条件成立，顶标就是一组“可行顶点标号”。

然后定义相等子图：只保留那些满足 lx[i] + ly[j] == w[i][j] 的边。KM算法有一个核心定理：如果在相等子图中存在完美匹配，那么这个匹配一定是原图的最大权完美匹配。

证明思路不复杂。任意一个合法完美匹配M，它的总权值一定不超过所有顶标之和，因为每条边都满足lx[i] + ly[j] >= w[i][j]，所以： sum(w(M)) <= sum(lx) + sum(ly) 而相等子图里的完美匹配M'，每条边都恰好取到lx[i] + ly[j]，所以： sum(w(M')) = sum(lx) + sum(ly) 于是M'达到上界，必然是最优解。

这个定理的含义是：问题从“直接找最大权匹配”转化成了“调整顶标，让相等子图慢慢长大，直到里面出现完美匹配”。谁都知道这个方向，但复杂度差异就藏在“调整顶标”这个细节里。

1.3 朴素KM为什么最坏是O(n^4)

最朴素的KM写法是这样的：对每个左侧点，尝试用DFS在相等子图上找增广路。如果当前相等子图找不到增广路，就计算一个delta，把当前交替树内的左侧点lx都减delta，把交替树内的右侧点ly都加delta，然后重新找增广路。

问题出在计算delta。朴素写法在增广失败后，会重新遍历所有左侧点x和所有右侧点y，找出满足“x在交替树内、y不在交替树内”的最小lx[x] + ly[y] - w[x][y]作为delta。这个找delta的过程是O(n^2)的。而每轮增广中，顶标可能要调整很多次，最坏情况下每个右侧点都要经过一次扩树才能进入交替树，所以一轮增广内部可能有O(n)次调整。外层有n个左侧点需要增广。于是复杂度近似： n（外层左侧点数量） * n（一轮内顶标调整次数） * n^2（每次找delta的扫描量） = O(n^4)

实际上，如果实现得特别粗糙，每次调整后还把所有vis数组清空重新DFS，那么单次DFS本身的O(n^2)扫描也会被乘进去，复杂度会更难看。很多人说KM算法是O(n^4)，就是从这里来的。

2. slack数组：把顶标更新从O(n^2)降到O(n)

2.1 一个关键观察

每次增广失败后，我们要找的delta本质上是：当前交替树内所有左侧点，到所有不在交替树内的右侧点之间，最小的“松弛量”： delta = min( lx[x] + ly[y] - w[x][y] )，其中x在树内，y不在树内

这个值在一次增广中并不需要反复从头计算。我们只需要对每个不在树内的y，记录到目前为止，树内所有x能给它的最小松弛量： slack[y] = min( lx[x] + ly[y] - w[x][y] )

这样找delta的时候就不需要遍历所有x和y了，只需要遍历一遍所有不在树内的y，取slack[y]的最小值。这一步从O(n^2)优化成了O(n)。

2.2 slack的维护过程

当一个左侧点x第一次被加入交替树时，它需要扫描所有不在树内的y，更新一遍这些y的slack值。这是不可避免的，因为x作为一个新顶点，可能给某些y提供更优的松弛量。

当顶标调整发生时，所有树内x的lx[i]都会减delta，所以对于所有不在树内的y，slack[y]都应该对应减delta。这是维护slack最核心的一步：不是重新计算，而是直接批量减。

这样一圈走下来，每轮增广中每个左侧点最多入树一次，扫描右侧点一次，总扫描量是O(n^2)。顶标调整最多发生O(n)次，每次调整的delta查找和维护都是O(n)。所以slack数组能把“找delta”这部分彻底降下来。

2.3 这里埋了一个“假O(n^3)”的坑

很多DFS版KM也用了slack数组，但它是这样做的：在while循环里，每次dfs失败后，清空所有visX和visY，然后从根左侧点重新开始dfs。表面上看slack让找delta变成了O(n)，但dfs本身又从头把已经访问过的顶点全部扫描了一遍。换句话说，顶标调整次数多的时候，前面的DFS工作全被清空重来，最坏情况下一轮增广仍然是O(n^3)，总复杂度仍然是O(n^4)。

这种做法我在题解里见过很多，作者都标注“O(n^3)”，但严格算是不成立的。它只是利用slack让实际常数变小，碰到精心构造的数据一样会超时。这也是为什么需要BFS版KM：BFS版里，交替树内的X和Y在一轮增广中不会被清掉，每个左侧点只入队一次、每个右侧点只被标记一次，这样才真正把一轮增广压到O(n^2)，乘以外层n个起点，总复杂度严格O(n^3)。

3. DFS递归版：能写，但别指望它是严格O(n^3)

3.1 经典的DFS+slack写法长什么样

如果你在网上搜KM模板，大概率会看到这样一个版本。它把匈牙利算法的DFS改一改，加一个slack数组就能跑：

bool dfs(int x) { visX[x] = 1; for (int y = 0; y < n; ++y) { if (visY[y]) continue; long long gap = lx[x] + ly[y] - w[x][y]; if (gap == 0) { visY[y] = 1; if (matchY[y] == -1 || dfs(matchY[y])) { matchY[y] = x; return true; } } else { slack[y] = min(slack[y], gap); } } return false; }

主流程是这样的：

for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) slack[j] = INF; while (true) { memset(visX, 0, sizeof(visX)); memset(visY, 0, sizeof(visY)); if (dfs(i)) break; long long delta = INF; for (int y = 0; y < n; ++y) if (!visY[y]) delta = min(delta, slack[y]); for (int x = 0; x < n; ++x) if (visX[x]) lx[x] -= delta; for (int y = 0; y < n; ++y) if (visY[y]) ly[y] += delta; for (int y = 0; y < n; ++y) if (!visY[y]) slack[y] -= delta; } }

这段代码很短，也很好背。很多题目用它能AC，是因为随机数据下增量比较均匀，while循环次数不会太多。但要注意，它有一个结构性问题：每次while循环，都memset清空visX和visY，然后重新dfs(i)。这意味着上一轮DFS已经扫描过的那批顶点全部作废，第二轮DFS会重新扫描一遍。如果顶标调整了很多次，光DFS的重复扫描就会累积出O(n^3)的单轮复杂度。

3.2 为什么这个写法最坏是O(n^4)

分析一下这个DFS版的复杂度。一次dfs，从根出发，会沿着相等子图递归搜索，最坏情况下访问到O(n)个左侧点和O(n)个右侧点，扫描边数O(n^2)。while循环每执行一次，至少有一个新的右侧点进入visY，所以while循环最多执行O(n)次。于是单个起点i的增广复杂度是： O(n)次while * O(n^2)次dfs扫描 = O(n^3) 外层一共n个起点，所以总复杂度O(n^4)。

有人可能会说：既然slack数组维护了未访问y的最小松弛度，为什么还要memset清空vis？因为DFS的递归逻辑要求visX和visY来防止重复访问，而KM调整顶标后，交替树理论上是可以继续生长的，但DFS版的实现没办法简单地保留之前的交替树继续搜索，最省事的办法就是清空重来。这恰恰是它退化的根源。

所以我的建议是：这个DFS版可以当成入门模板来理解KM原理，但如果你要应对大数据量，或者你负责的项目里KM会被反复调用，还是看下面的BFS版更稳。

4. BFS迭代版：真正的O(n^3)写法与完整模板

4.1 为什么BFS能做到严格O(n^3)

BFS版的思路是：在一轮增广中，交替树不是通过递归不断回溯，而是通过队列逐层扩展。每个左侧点一旦进入队列，就被标记visX；每个右侧点一旦被访问，就被标记visY。一轮增广内，这些标记不会清空，哪怕顶标调整了很多次，已经被访问过的点也不会重新扫描。

这意味着在一轮增广中：

• 每个左侧点最多入队一次，每个左侧点最多扫描一次所有右侧点；
• 每个右侧点最多被标记一次；
• 顶标调整最多发生O(n)次，每次调整O(n)；
• 所以一轮增广的复杂度严格O(n^2)。

外层n个起点，总复杂度O(n^3)。这个才是真正的O(n^3)。

BFS版的代码比DFS版复杂的地方在于，它必须额外维护一个pre数组来记录交替树中每个右侧点是从哪个左侧点过来的。增广成功后，沿着pre数组反向回溯就能更新匹配。

4.2 核心数据结构与C++模板

看代码之前，先把变量明确一下。我的模板里用matchX[i]表示左侧点i当前匹配的右侧点，matchY[j]表示右侧点j当前匹配的左侧点。两者互为反函数，都要维护。pre[j]表示在交替树中右侧点j的“前驱左侧点”。slack[j]就是前面说的松弛数组。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = (1LL << 60); const int MAXN = 505; int n; ll w[MAXN][MAXN]; ll lx[MAXN], ly[MAXN]; int matchX[MAXN], matchY[MAXN]; int pre[MAXN]; bool visX[MAXN], visY[MAXN]; ll slack[MAXN]; bool km_bfs(int root) { fill(pre, pre + n, -1); for (int j = 0; j < n; ++j) slack[j] = INF; memset(visX, 0, sizeof(visX)); memset(visY, 0, sizeof(visY)); queue<int> q; q.push(root); visX[root] = 1; while (true) { while (!q.empty()) { int x = q.front(); q.pop(); visX[x] = 1; for (int y = 0; y < n; ++y) { if (visY[y]) continue; ll gap = lx[x] + ly[y] - w[x][y]; if (gap < slack[y]) { slack[y] = gap; pre[y] = x; } if (gap == 0) { visY[y] = 1; if (matchY[y] == -1) { int curY = y; while (curY != -1) { int x0 = pre[curY]; int nextY = matchX[x0]; matchY[curY] = x0; matchX[x0] = curY; curY = nextY; } return true; } int nxt = matchY[y]; if (!visX[nxt]) { visX[nxt] = 1; q.push(nxt); } } } } // 队列为空，说明当前相等子图无法继续扩展，需要调整顶标 ll delta = INF; for (int y = 0; y < n; ++y) if (!visY[y]) delta = min(delta, slack[y]); if (delta == INF) return false; // 不存在完美匹配 for (int i = 0; i < n; ++i) if (visX[i]) lx[i] -= delta; for (int j = 0; j < n; ++j) if (visY[j]) ly[j] += delta; for (int j = 0; j < n; ++j) if (!visY[j]) slack[j] -= delta; // 把所有 slack 变为0的未访问Y点加入交替树 for (int y = 0; y < n; ++y) { if (!visY[y] && slack[y] == 0) { visY[y] = 1; if (matchY[y] == -1) { int curY = y; while (curY != -1) { int x0 = pre[curY]; int nextY = matchX[x0]; matchY[curY] = x0; matchX[x0] = curY; curY = nextY; } return true; } int nxt = matchY[y]; if (!visX[nxt]) { visX[nxt] = 1; q.push(nxt); } } } } } ll KM() { for (int i = 0; i < n; ++i) { lx[i] = -INF; for (int j = 0; j < n; ++j) lx[i] = max(lx[i], w[i][j]); } for (int j = 0; j < n; ++j) ly[j] = 0; memset(matchX, -1, sizeof(matchX)); memset(matchY, -1, sizeof(matchY)); for (int i = 0; i < n; ++i) { if (!km_bfs(i)) { // 说明无完美匹配，按题目要求处理 return -INF; } } ll ans = 0; for (int y = 0; y < n; ++y) if (matchY[y] != -1) ans += w[matchY[y]][y]; return ans; }

4.3 代码里几个必须注意的位置

第一，pre[y]的更新时机。当某个左侧点x看到右侧点y时，如果gap比当前slack[y]小，就更新slack[y]并把pre[y]设为x。这意味着pre[y]记录的是能让slack[y]达到当前最小值的那个左侧点。后面回溯增广路径时，必须依赖pre数组，否则你会找不到是从哪条路走到y的。

第二，修改顶标后，不要清空visX和visY，也不要重新初始化slack。这里的slack[y]只是统一减delta，表示所有已访问左侧点的lx都减了delta。这个批量操作是O(n)的，也是严格O(n^3)的关键。写代码时最容易犯的错，就是在调整顶标后又重新memset，那样等于把优化全丢了。

第三，delta可能为INF。当图本身不保证存在完美匹配时，比如某个左侧点没有任何连边，它的lx会一直是-INF，slack也会是INF，此时delta会算成INF，函数应该提前返回无解，否则会死循环。

4.4 关于边权为负和非完备匹配的一点说明

很多人问KM能不能处理负权边。可以，KM根本不要求边权非负，只要存在完美匹配且初始化时lx[i]取的是第i行最大的w值，即使最大值为负数也没有关系。需要注意的只是在初始化lx时不能初始化为0就完事，否则会丢失“这个点可能只能匹配负权边”的信息。

如果题目不是要求完美匹配，而是只要求最大权匹配，比如某些点可以空闲不匹配，那么直接用上面的KM模板会出问题，因为KM强制每个点都被匹配。这种场景一种常见做法是把不存在的边权设成0再跑KM，但严格说这么做只有在两边点数相同时才安全，而且可能选出0权边造成虚假匹配。如果你在项目里遇到“允许点不匹配”的带权匹配，我更推荐直接用费用流或者改造成标准完备匹配模型，别想着靠补0边蒙混。

5. 常见问题与实战踩坑记录

5.1 递归DFS版爆栈问题

如果n达到几千，DFS递归深度可能到n，递归栈很容易爆掉。BFS版没有这个问题，因为它用的是迭代队列。这也是我在工程项目里倾向BFS版的原因之一。很多算法比赛里n可能只有两三百，DFS版也能过，但当你把KM封装成一个公共模块、在服务端处理更大规模数据时，就必须考虑这个问题。

5.2 匹配数组只维护一半导致的回溯错误

有些人只维护matchY，不维护matchX，回溯修改时只做matchY的下标变换，然后发现答案偶尔不对。KM的回溯本质上是在交替树上沿着pre数组反向提款，必须同时知道“某个左侧点之前匹配的是哪个右侧点”，这就要靠matchX。只维护一半，回溯链是走不完整的。所以我的模板里matchX和matchY成对维护，建议你也这么做。

5.3 边权矩阵用0表示“无边”的坑

有些题目输入里不存在的边权可能用0占位，也可能是负数。如果你的初始化把“无边”也当成权值0去参与lx初始化，可能会出现错误匹配。稳妥做法是给无边位置赋一个足够小的负数，比如-INF，并且在初始化lx时只取真正有边存在的最大值。如果一整行都没有边，那可以直接判定无解。

5.4 long long与INF的边界

KM里面lx、ly、slack、delta都可能累加很多轮。如果边权是int范围但n有几百，顶标值可能超过int。我建议把所有相关变量都开long long，INF设成1e18的量级，避免在减delta时溢出。这一点在很多题目里都很关键，尤其当边权本身就有负数时，INF不能太大，否则减法直接溢出成未定义行为。

5.5 调试KM匹配结果的小技巧

我实际调试KM时有一个习惯：跑完一遍之后，检查两个约束是否同时成立。第一，对每一对已匹配边，确认matchY[j]与matchX[i]互为反函数，也就是没有两个右侧点匹配到同一个左侧点。第二，对所有i和j，验证lx[i] + ly[j] >= w[i][j]始终成立。如果第二个条件被破坏，说明顶标更新写错了，最常见的就是修改顶标后忘了把树内右侧点的ly加上去，或者树内左侧点的lx减多了。

如果跑出来答案偏大，通常是匹配关系没更新对，导致统计时重复计算了某条边。如果答案偏小，一般是初始化lx时没有取到真正的最大值，或者slack数组初值不对。

5.6 一组可以自测的数据

不说题目来源，只给一个我经常用来验证KM模板正确性的小样例，方便你写完代码后自查。三行三列，边权矩阵：

1 2 3 2 4 6 3 6 9

这个矩阵实际上每一列都是线性相关的，最大权完美匹配一眼能看出来就是选(0,2)、(1,1)、(2,0)或者(0,0)、(1,1)、(2,2)这类组合，最大和是3+4+3=10，或者1+4+9=14？细心算一下应该是14，因为选(0,2)=3，(1,1)=4，(2,0)=3，总和是10；但如果选(0,2)=3，(1,2)不能重，所以(1,1)=4，(2,0)=3是10。如果选(0,0)=1，(1,1)=4，(2,2)=9，总和14。再看选(0,1)=2，(1,2)=6，(2,0)=3，总和11。所以正确答案应该是14。跑一下模板，输出14就说明基本功能正常。如果输出别的，优先检查matchX和matchY的回溯。

5.7 工程里什么时候该用KM，什么时候别用

KM只适用于两边点数相同且需要完美匹配的带权二分图。如果你的数据规模特别大，比如n到几万，O(n^3)也扛不住，这时候得考虑专门的逼近算法、分布式实现或者干脆用匈牙利加费用流。如果图特别稀疏，KM的O(n^3)也是基于稠密分析的，稀疏图用费用流可能实际更快。KM的优势在于实现简洁、理论复杂度稳定，适合中等规模、图较稠密的场景。

我自己在多个项目里用到KM，最典型的就是多目标跟踪中的数据关联：左边是已有轨迹，右边是当前帧检测目标，边权表示轨迹和检测的相似度，KM求出全局最优的最大权匹配。这种场景下n往往不会特别大，但会高频率反复调用，所以一个严格O(n^3)、不会在最坏数据下失控的模板特别重要。

最后分享一个小经验：写KM的时候，如果发现某个数据跑出来不对，不要急着调顶标参数，先把slack数组在每次调整顶标之后打印出来，和手工算一遍对比。我调试时发现，十次里有九次是忘记在每次DFS失败后更新未访问Y的slack值，而这个问题用BFS版就不容易犯，因为它把“批量更新slack”这一步骤从逻辑里显式写出来了。这也是我最终完全切换到这个BFS写法的原因。