实现：从slack优化到BFS版完整模板)
先聊一个很多人踩过的认知坑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所以对于所有不在树内的yslack[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版KMBFS版里交替树内的X和Y在一轮增广中不会被清掉每个左侧点只入队一次、每个右侧点只被标记一次这样才真正把一轮增广压到O(n^2)乘以外层n个起点总复杂度严格O(n^3)。3. DFS递归版能写但别指望它是严格O(n^3)3.1 经典的DFSslack写法长什么样如果你在网上搜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)); queueint 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会一直是-INFslack也会是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 longINF设成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)这类组合最大和是34310或者14914细心算一下应该是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写法的原因。
先聊一个很多人踩过的认知坑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所以对于所有不在树内的yslack[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版KMBFS版里交替树内的X和Y在一轮增广中不会被清掉每个左侧点只入队一次、每个右侧点只被标记一次这样才真正把一轮增广压到O(n^2)乘以外层n个起点总复杂度严格O(n^3)。3. DFS递归版能写但别指望它是严格O(n^3)3.1 经典的DFSslack写法长什么样如果你在网上搜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)); queueint 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会一直是-INFslack也会是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 longINF设成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)这类组合最大和是34310或者14914细心算一下应该是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写法的原因。
的KM算法BFS模板：从顶标到增广全解析)
