稳定O(n^3)的KM算法BFS模板：从顶标到增广全解析

说个挺常见的现象网上搜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要求两边相等都是nlx[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] - deltaT中所有右点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到当前交错树的最小gapslack[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就更新slackgap等于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到当前交错树的最小gappre[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 - 右bpre记录会让pre[b] apre[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求最大权匹配但允许左点剩余补虚拟点真实不存在的边填04.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. 常见问题与调试经验速查下面这些坑我基本都踩过整理成速查表方便定位。现象可能原因处理方式答案比暴力枚举小缺边补0而不是补-INF确认题意是不是必须完美匹配答案比暴力枚举大顶标维护错误匹配边不在相等子图检查更新顶标是否对所有matchy[v]左点减delta死循环pre更新条件写反或下标从0开始导致哨兵冲突下标从1开始matchy[0]只存根左点TLE用了递归DFS版且每次失败后重新find换成BFS版负权图结果异常初始化lx[i]用了0而不是每行最大值lx[i]初始化为-INF再取max5.1 结果对不上暴力枚举写KM最容易出的问题就是“答案看起来差不多但和暴力差一截”。我建议在小数据上直接随机生成权值然后暴力枚举所有排列验证。n不超过8时全排列算一遍很快能把大部分实现错误暴露出来。验证时不要把KM结果和某个“感觉上正确的答案”比要严格比暴力全排列。一旦发现不相等首选检查点就是顶标更新代码是不是只减了当前左点而漏掉了之前的左点。5.2 权值范围很大时的INF选择如果边权最大是1e9n是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接近1000O(n^3)的常数会比较大BFS版仍然有压力。此时可以优化枚举右点的循环每轮bfs里只扫有边权的列或者把矩阵转置一下让访问更连续。多数情况下500以内的n用这份模板问题不大超过800就要特别小心常数了。KM这套顶标思想本身并不难难的是写法的严谨性。DFS版直观但容易退化BFS版绕了一点但复杂度可控。如果你之前只在板子上背过DFS下一次不妨换成BFS版试试跑几组极限数据就能体会到区别。