写带权二分图匹配KM算法是个绕不过去的名字。尤其是刚接触“工人-任务”这类分配问题时很多人第一反应就是上KM左侧是人右侧是任务边权是效率或收益最后要的是一组完美匹配让总收益最大。网上流传最广的模板是DFS加slack数组的写法虽然已经比最原始的O(n^4)快了不少但真扔到几千个点的稠密图上还是能明显感觉到卡顿。这篇文章我会从KM算法的数学原理开始逐步讲清楚传统slack优化为什么还不够快再给出一套基于BFS迭代的更快写法并用实际压力测试数据做对比。想彻底搞懂KM为什么能求出最大权匹配以及怎么把常数压到最小这篇应该能帮到你。1. 先把KM的核心思想讲透1.1 最大权完美匹配到底在求什么先说问题定义。给定一个二分图左部有n个点右部有n个点每条边有一个权值w[i][j]。要找一组匹配让每个左点恰好匹配一个右点每个右点也恰好匹配一个左点这就是完美匹配。如果希望匹配中所有边的权值和最大就叫最大权完美匹配。最直观的做法是暴力枚举所有排列n个点的排列数量是n!n10就受不了。KM算法解决的就是这个问题它不直接枚举匹配而是借用“顶标”和“相等子图”两个工具把带权匹配问题转化成一系列不带权的完美匹配判断。顶标是这样定义的给每个左点分配一个值lx[i]给每个右点分配一个值ly[j]要求对于任意边(i,j)都满足lx[i] ly[j] w[i][j]满足这个条件的顶标称为可行顶标。初始时可以让所有ly[j]0令每个lx[i]等于它邻接边中的最大权值这样一整组顶标天然满足条件。接下来构建相等子图只在满足lx[i] ly[j] w[i][j]的边上保留连接。KM算法的关键结论是如果在相等子图里能找到完美匹配那这个匹配一定是原图的最大权完美匹配。证明也不复杂。假设M是相等子图里的一个完美匹配那么M中每条边都满足等号关系所以M的总权值正好等于所有顶标之和sum_w(M) sum(lx[i] ly[j]) for each matched edge sum_lx sum_ly再看任意一个完美匹配M由于每条边都满足不等式lx[i] ly[j] w[i][j]而完美匹配中每个点恰好出现一次所以sum_w(M) sum_lx sum_ly sum_w(M)也就是说相等子图里的任何完美匹配权值都大于等于其它所有完美匹配。问题就从“找最大权匹配”变成了“找一组可行顶标使得对应相等子图里存在完美匹配”。1.2 交错树与松弛量的作用如何在相等子图里找完美匹配基础工具是匈牙利算法它通过交替路径和增广路来扩展匹配。区别在于KM算法在跑匈牙利算法的过程中如果当前相等子图里找不到完美匹配就需要调整顶标把更多边拉进相等子图。怎么理解这个过程假设从某个未匹配左点出发在相等子图中尝试寻找增广路。每次递归走过的左点集合记为S右点集合记为T这些点组成的树就是交错树。如果搜索失败说明交错树中所有可达右点都已经匹配没有再往外的路。这时候计算一个关键值deltadelta min{ lx[i] ly[j] - w[i][j] } 其中 i 属于 Sj 不属于 T然后做一次顶标调整对于所有 i 属于 Slx[i] - delta 对于所有 j 属于 Tly[j] delta为什么这样调整有效可以从三个角度看第一原来的相等子图边不会退出。匹配边如果存在它的两个端点一定同属于S或T否则右点会被加入交错树所以lx[i]ly[j]要么不变要么同时增减仍然保持相等关系。第二至少有一条从S到T外右点的新边会变成相等边因为delta取的就是最小差值。第三顶标的可行性不会破坏因为对于任意边如果左点i在S中右点j不在T中差值减少delta其它组合不变或增加仍然满足 w。整个KM算法就是一个循环在相等子图里跑增广路失败就调整顶标再跑直到找到完美匹配。这个框架不难难的是怎么把delta高效算出来。2. 传统slack优化为什么还不够快2.1 朴素实现的复杂度是O(n^4)最原始的实现是每次增广失败后暴力枚举所有S内左点和所有T外右点计算最小的lx[i]ly[j]-w[i][j]。这个枚举是O(n^2)。调整顶标之后搜索路径可能仍然失败需要再次枚举。每个左点最多需要成功增广一次而一次增广可能调整多次顶标最坏情况下总复杂度O(n^4)。n小的时候感觉不到n到200就开始明显变慢n到500基本会卡住。这也是后来大家普遍改用slack优化数组的原因。2.2 slack数组优化的核心思路slack优化的想法很直接不要每次重新枚举S所有点找delta而是用一个数组记录“当前交错树内每个左点到某个未访问右点的最小松弛量”。定义slack[j] min{ lx[i] ly[j] - w[i][j] } 其中 i 是当前已访问左点每次DFS扩展一个新的左点x时用x的所有出边去更新这个数组if (gap slack[j]) { slack[j] gap; pre[j] x; }pre[j]记录的是“哪个左点给了右点j当前最小的松弛量”后面回溯增广路时要靠它。这样找全局delta就只需要扫描所有未访问右点delta min{ slack[j] } (j未访问)顶标调整后因为所有S内左点的lx都减了delta而T外右点的ly不变所以所有未访问右点的slack值也要统一减deltaif (!visy[j]) slack[j] - delta;这个优化把每次调整顶标的代价从O(n^2)降到O(n)左右整体复杂度变成O(n^3)。这也是绝大多数KM模板使用的版本。2.3 传统DFS加slack写法中的隐藏开销看起来O(n^3)已经很好但实际跑起来DFS加slack的模板有几个问题。第一个问题是重复扫描。每次增广失败、调整顶标后很多模板会清空vis数组重新从起点执行DFS。这意味着起点以及之前已经访问过的左点它们的出边会被再次扫描。即使使用slack数组缓存了松弛量也仍然需要重新走一遍递归树很多重复计算隐藏在这层“递归回溯”里。第二个问题是递归栈。max权匹配的增广路最长可能达到nDFS递归深度也会达到n。在n2000的稠密图上即使没有爆栈大量递归调用本身也带来不小的常数。第三个问题是更新slack时全量遍历。调整顶标后要遍历一次所有未访问右点做slack[j] - delta这是O(n)的。单看还好但一轮增广可能调整多次累积起来也不小。所以我一直觉得传统DFS加slack只是“能过的O(n^3)”离“最优实现”还有距离。下面要讲的BFS迭代写法核心思路是让每个左点只被扫描一次并且完全去掉递归。3. 更快的优化BFS迭代版KM算法3.1 核心改进点解析我把这套更快写法称为BFS迭代版本质还是slack优化但实现细节完全不同。传统DFS的问题在于增广失败后为了继续找增广路必须递归回溯并重新搜索。而BFS版把每个左点放进队列从左往右逐层扩展。每个已访问的左点只出队一次只扫描它的出边一次没有重复劳动。同时slack数组维护的含义不变仍然是“树内左点到未访问右点的最小松弛量”。但BFS版不依赖递归而是通过一个明确的循环反复执行两个动作从队列中取出左点用它的出边更新slack和pre查找最小的slack调整顶标再把新暴露的匹配左点入队整个过程更像是在“走路”而不是在“递归回溯”。另一个重要的改进是pre数组的使用。在DFS版里pre通常用于记录slack更新来源在BFS版里pre同样是记录“某个右点当前最小松弛量来自哪个左点”。找到未匹配右点后沿着pre链就能还原整条增广路。3.2 BFS版增广流程详解拿一次增广举例。假设当前要给左点st找匹配。第一步初始化。清空visx、visy把slack全部置INFpre重置为空队列里放入st标记visx[st]true。第二步扩展队列。只要队列不为空就取出队首左点x枚举所有未访问右点y计算gapgap lx[x] ly[y] - w[x][y]如果gap比slack[y]小就更新slack[y]同时设置pre[y]x。第三步找最小松弛量。在所有未访问右点中选出slack[j]最小的那个记为y同时得到delta。第四步如果delta大于0就调整顶标S内左点 lx - delta T内右点 ly delta 未访问右点 slack - delta注意这一步不会破坏slack数组的累积含义因为所有未访问右点的slack都统一减少了delta。调整之后刚选中的y因为松弛量为0变成了一条新增的相等边。第五步标记y为已访问。如果y还没有匹配说明找到了一个未匹配右点增广路到此为止沿pre链回溯并翻转匹配即可。如果y已经匹配了左点x2那么把x2入队标记visx[x2]true继续下一轮扩展。这个流程中每个左点最多入队一次每个右点也最多被访问一次。每次处理完队列后查找delta需要扫描所有右点O(n)。整个增广过程最多扩展n个左点所以单次增广是O(n^2)总共n次增广复杂度O(n^3)。虽然理论复杂度没变但常数比DFS版小得多。3.3 可直接使用的C实现下面是我常驻的一套BFS版KM实现n是点数1-index权值矩阵用w[i][j]存。这里假设左右点数相等且一定有完美匹配实际工程中如果点数不等或者可能不满需要先补点补边。#include bits/stdc.h using namespace std; const long long INF 1e18; const int N 2005; long long w[N][N], lx[N], ly[N], slack[N]; int matchx[N], matchy[N], pre[N]; bool visx[N], visy[N]; bool bfs(int st, int n) { queueint q; while (!q.empty()) q.pop(); fill(visx 1, visx n 1, false); fill(visy 1, visy n 1, false); fill(slack 1, slack n 1, INF); fill(pre 1, pre n 1, 0); q.push(st); visx[st] true; while (true) { while (!q.empty()) { int x q.front(); q.pop(); for (int y 1; y n; y) { if (visy[y]) continue; long long gap lx[x] ly[y] - w[x][y]; if (gap slack[y]) { slack[y] gap; pre[y] x; } } } int y -1; long long delta INF; for (int j 1; j n; j) { if (!visy[j] slack[j] delta) { delta slack[j]; y j; } } if (delta 0) { for (int i 1; i n; i) { if (visx[i]) lx[i] - delta; if (visy[i]) ly[i] delta; } for (int j 1; j n; j) { if (!visy[j]) slack[j] - delta; } } visy[y] true; int x matchy[y]; if (x -1) { // 找到未匹配右点沿pre链翻转 while (y ! -1) { int px pre[y]; int ny matchx[px]; matchx[px] y; matchy[y] px; y ny; } return true; } else { visx[x] true; q.push(x); } } } long long km(int n) { fill(matchx 1, matchx n 1, -1); fill(matchy 1, matchy n 1, -1); fill(ly 1, ly n 1, 0); 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]); } } for (int i 1; i n; i) { bfs(i, n); } long long ans 0; for (int i 1; i n; i) { ans w[i][matchx[i]]; } return ans; }这个实现里有一点需要特别注意matchx[i]表示左点i匹配的右点初始为-1matchy[j]表示右点j匹配的左点初始也为-1。在bfs函数里找到未匹配右点后回溯沿pre链走到最后一个左点时matchx[px]一定是-1此时把ny置为-1循环自然结束。这里用-1而不是0能让逻辑更清晰但同时要求所有数组初始化时都统一用-1。还有一点在回溯翻转时pre[y]记录的左点一定是已经在交错树里的左点。比如根节点st它最初没有匹配所以当某个右点通过st的边被更新slack时pre[y]会等于st。翻转时先让st匹配上这个右点再顺着原来的匹配关系继续替换直到遇到某个原本没有匹配的左点。4. 复杂度对比和实测差距4.1 理论上为什么BFS更快先明确复杂度朴素实现O(n^4)每次找delta都枚举S和T外的所有组合。DFS加slackO(n^3)用slack数组缓存松弛量。BFS版本O(n^3)但常数明显更小。理论复杂度和DFS版相同为什么实际更快关键在于重复扫描次数。DFS版的一次增广如果第一次DFS失败调整顶标的完整过程是这样的先把slack更新一遍再清空vis重新从起点DFS。第二次DFS会再次把起点以及之前已经访问过的左点的出边扫描一遍。虽然slack数组保住了松弛量但扫描出边的开销重复发生了。如果一轮增广中调整了多次顶标重复扫描的次数会等比放大。BFS版不会这样。每个左点入队后它的出边只会被扫描一次之后无论调整多少次顶标都不会再重扫这个左点。整个一轮增广中每个左点最多入队一次扫描量是O(n^2)而不是“调整次数乘以n^2”。这在实际稠密图里带来的提升非常明显。另外BFS版没有递归函数不存在递归栈顶爆掉的问题也省去了大量函数调用开销。对于n1000以上的图这两点叠加起来运行时间往往能差出好几倍。4.2 一组实际压力测试我用随机的稠密图做过几组对比测试数据是完全二分图边权随机生成机器是普通台式机不涉及任何特定平台。为了公平两种实现都开了O2优化DFS版的递归深度足够不会爆栈。在n500时DFS加slack大约需要0.8秒BFS版本大约0.3秒。n1000时DFS版已经接近2秒BFS版本不到0.7秒。到n2000时DFS版跑到了7秒开外BFS版本还能压在2.5秒左右。这个差距会随着n增长继续扩大主要就是重复扫描和递归调用堆出来的常数。当然这不是说DFS版毫无价值。DFS版代码结构更简单适合在n比较小、或者比赛时间不紧的时候快速敲出来。但如果你的场景是n超过1000的稠密图BFS版本非常值得常驻在模板库中。4.3 是不是越复杂越“吊打”标题里用了“吊打”说实话有点标题党。BFS版本本质上还是slack优化只是把实现方式从递归换成迭代减少了重复扩展。它并没有改变O(n^3)的上界。我也见过有人在此基础上再用堆或线段树查最小slack想进一步压缩查找delta的O(n)扫描。这里要泼一盆冷水在完全稠密图里每个左点入队后仍然要扫描n条出边更新slack所以每轮增广的扫描量至少是O(n^2)。堆优化能把查delta从O(n)降到O(log n)但更新slack时每条边仍要push总复杂度会变成O(n^3 log n)理论反而更差。实测下来堆优化在n不大时稍微快一点点n大了以后经常比线性扫描慢。所以我不建议盲目上堆。真正值得投入时间的是BFS加slack数组、pre回溯、尽可能减少fill次数的这套写法。它已经是工程上很均衡的方案。5. 常见问题和避坑实录5.1 slack数组不初始化的后果很多新手把DFS模板改成BFS时会忘记在每轮增广前把slack数组初始化成INF。这样上一轮残留的松弛量会影响本轮判断可能让delta算出一个错误的小值导致顶标调整不足相等子图没有真正扩大。我通常会在bfs函数开头一次性reset五样东西visx、visy、slack、pre、队列。虽然初始化也是O(n)但相比整个增广过程微不足道。千万别为了省一点memset时间而省略初始化一旦出bug非常难查。5.2 回溯pre链时最容易写错pre数组的含义是“右点j当前最小松弛量由哪个左点产生”不是“交错树中右点的前一个右点”。有些人会把它和普通匈牙利算法的match路径搞混导致回溯时乱套。正确的回溯方式是这样从最终找到的未匹配右点y开始找到产生它的左点px这个左点原本匹配的右点是ny然后让px匹配yy匹配px接着把y更新为ny继续。每一步都是“右点向前找左点左点再换右点”直到遇到某个左点原本没有匹配。如果pre记录错了翻转出来的匹配会不合法甚至死循环。建议写完以后用一个3到4个点的小数据手工推一遍。5.3 非方阵图和缺失边怎么处理KM算法要求左右点数相等而且通常默认一定存在完美匹配。如果你的实际输入左右点数不等或者有些边不存在需要先补一个完整图。左右点数不等时在点数较少的一侧补虚拟点让两边都是n个点。缺失的边补成0权边。这样跑出来的匹配如果包含了虚拟边说明实际没有完美匹配需要业务层自己判断。注意补0权边适用于“最大权匹配不要求完美”的场景你希望尽量选高收益边那么0边可以让那些本来不该匹配的虚拟配对不增加总收益。但如果原始边权本身有负值并且你希望完美匹配里避开负边直接把缺失边补成0还不够更稳妥的做法是先把所有边权平移确保没有负权或者改用费用流。负权边的问题本质上是KM的顶标初始化方式决定的lx初始取每行最大值ly初始为0。如果某行全是负权lx会变成负数虽然仍然可行但相等子图里可能不存在任何边算法会一直在调整顶标。处理这类情况时我建议先把边权做一次整体平移让最小边权变成0再跑KM。5.4 浮点权值下的精度陷阱KM算法依赖“相等”这个强判断。如果边权是浮点数lx[i]ly[j]-w[i][j]因为浮点误差很难精确等于0。这时需要给gap判断加一个EPS通常取1e-9或1e-10认为绝对值小于EPS就算相等。但即使加了EPS浮点KM也比较脆弱因为delta的更新和slack的累积会不断放大误差。如果非用不可建议统一用long double并把所有非零判断都改成与EPS比较。如果图比较稀疏或者边权是浮点数但数据量不大我个人更推荐用最小费用最大流来求最大权匹配它不会因为精度问题陷入死循环。5.5 如何判断不存在完美匹配KM并不能直接告诉你“匹配不存在”。当算法跑完全部左点某些左点仍然没有匹配时就是不存在完美匹配。这时候matchx里会有-1。更早的判断方法是先跑一遍不带权的匈牙利算法看看最大匹配数是否等于n。如果不是n直接放弃KM。这个预检是O(n^3)但常数很小能帮你避免在KM里调顶标调出问题。另外补虚拟点时也要注意。如果原始图有个左点孤立无邻边补0边后它可能会匹配到虚拟右点。业务层面要知道这个结果代表“没有人愿意接这个任务”而不是真实分配。5.6 时间戳优化要不要加BFS版本最耗时的其实是fill数组。如果你追求极致性能可以用时间戳替代visx、visy的fill操作用curTime的方式判断是否访问过。slack和pre依然要每轮重置。实际测试里时间戳优化能省一点fill时间但不会像从DFS换成BFS那样带来量级变化。我一般建议先把BFS版本写对再用性能分析工具看瓶颈在哪里。如果fill占比很高再上时间戳不迟。最后分享一个实用经验我最初写KM时也迷信DFS加slack就是最优解直到某次处理一个n1200的稠密图DFS版跑了很久还时不时抖动换成BFS版以后稳定了许多。后来再遇到类似分配问题我默认就会用BFS版这套模板。如果你正在给某个实际系统做排班或任务分配还有一个小建议不要一上来就KM。先确认数据规模。n在100以下朴素DFS都无所谓n到了几百上千再上KM。而且KM对完美匹配的要求很严格如果业务允许“有人闲着没任务”最好把模型改成允许虚拟匹配或者直接上费用流否则算法会在边界条件上吃掉你大量时间。希望这篇能帮你少走一些弯路。 写带权二分图匹配KM算法是个绕不过去的名字。尤其是刚接触“工人-任务”这类分配问题时很多人第一反应就是上KM左侧是人右侧是任务边权是效率或收益最后要的是一组完美匹配让总收益最大。网上流传最广的模板是DFS加slack数组的写法虽然已经比最原始的O(n^4)快了不少但真扔到几千个点的稠密图上还是能明显感觉到卡顿。这篇文章我会从KM算法的数学原理开始逐步讲清楚传统slack优化为什么还不够快再给出一套基于BFS迭代的更快写法并用实际压力测试数据做对比。想彻底搞懂KM为什么能求出最大权匹配以及怎么把常数压到最小这篇应该能帮到你。1. 先把KM的核心思想讲透1.1 最大权完美匹配到底在求什么先说问题定义。给定一个二分图左部有n个点右部有n个点每条边有一个权值w[i][j]。要找一组匹配让每个左点恰好匹配一个右点每个右点也恰好匹配一个左点这就是完美匹配。如果希望匹配中所有边的权值和最大就叫最大权完美匹配。最直观的做法是暴力枚举所有排列n个点的排列数量是n!n10就受不了。KM算法解决的就是这个问题它不直接枚举匹配而是借用“顶标”和“相等子图”两个工具把带权匹配问题转化成一系列不带权的完美匹配判断。顶标是这样定义的给每个左点分配一个值lx[i]给每个右点分配一个值ly[j]要求对于任意边(i,j)都满足lx[i] ly[j] w[i][j]满足这个条件的顶标称为可行顶标。初始时可以让所有ly[j]0令每个lx[i]等于它邻接边中的最大权值这样一整组顶标天然满足条件。接下来构建相等子图只在满足lx[i] ly[j] w[i][j]的边上保留连接。KM算法的关键结论是如果在相等子图里能找到完美匹配那这个匹配一定是原图的最大权完美匹配。证明也不复杂。假设M是相等子图里的一个完美匹配那么M中每条边都满足等号关系所以M的总权值正好等于所有顶标之和sum_w(M) sum(lx[i] ly[j]) for each matched edge sum_lx sum_ly再看任意一个完美匹配M由于每条边都满足不等式lx[i] ly[j] w[i][j]而完美匹配中每个点恰好出现一次所以sum_w(M) sum_lx sum_ly sum_w(M)也就是说相等子图里的任何完美匹配权值都大于等于其它所有完美匹配。问题就从“找最大权匹配”变成了“找一组可行顶标使得对应相等子图里存在完美匹配”。1.2 交错树与松弛量的作用如何在相等子图里找完美匹配基础工具是匈牙利算法它通过交替路径和增广路来扩展匹配。区别在于KM算法在跑匈牙利算法的过程中如果当前相等子图里找不到完美匹配就需要调整顶标把更多边拉进相等子图。怎么理解这个过程假设从某个未匹配左点出发在相等子图中尝试寻找增广路。每次递归走过的左点集合记为S右点集合记为T这些点组成的树就是交错树。如果搜索失败说明交错树中所有可达右点都已经匹配没有再往外的路。这时候计算一个关键值deltadelta min{ lx[i] ly[j] - w[i][j] } 其中 i 属于 Sj 不属于 T然后做一次顶标调整对于所有 i 属于 Slx[i] - delta 对于所有 j 属于 Tly[j] delta为什么这样调整有效可以从三个角度看第一原来的相等子图边不会退出。匹配边如果存在它的两个端点一定同属于S或T否则右点会被加入交错树所以lx[i]ly[j]要么不变要么同时增减仍然保持相等关系。第二至少有一条从S到T外右点的新边会变成相等边因为delta取的就是最小差值。第三顶标的可行性不会破坏因为对于任意边如果左点i在S中右点j不在T中差值减少delta其它组合不变或增加仍然满足 w。整个KM算法就是一个循环在相等子图里跑增广路失败就调整顶标再跑直到找到完美匹配。这个框架不难难的是怎么把delta高效算出来。2. 传统slack优化为什么还不够快2.1 朴素实现的复杂度是O(n^4)最原始的实现是每次增广失败后暴力枚举所有S内左点和所有T外右点计算最小的lx[i]ly[j]-w[i][j]。这个枚举是O(n^2)。调整顶标之后搜索路径可能仍然失败需要再次枚举。每个左点最多需要成功增广一次而一次增广可能调整多次顶标最坏情况下总复杂度O(n^4)。n小的时候感觉不到n到200就开始明显变慢n到500基本会卡住。这也是后来大家普遍改用slack优化数组的原因。2.2 slack数组优化的核心思路slack优化的想法很直接不要每次重新枚举S所有点找delta而是用一个数组记录“当前交错树内每个左点到某个未访问右点的最小松弛量”。定义slack[j] min{ lx[i] ly[j] - w[i][j] } 其中 i 是当前已访问左点每次DFS扩展一个新的左点x时用x的所有出边去更新这个数组if (gap slack[j]) { slack[j] gap; pre[j] x; }pre[j]记录的是“哪个左点给了右点j当前最小的松弛量”后面回溯增广路时要靠它。这样找全局delta就只需要扫描所有未访问右点delta min{ slack[j] } (j未访问)顶标调整后因为所有S内左点的lx都减了delta而T外右点的ly不变所以所有未访问右点的slack值也要统一减deltaif (!visy[j]) slack[j] - delta;这个优化把每次调整顶标的代价从O(n^2)降到O(n)左右整体复杂度变成O(n^3)。这也是绝大多数KM模板使用的版本。2.3 传统DFS加slack写法中的隐藏开销看起来O(n^3)已经很好但实际跑起来DFS加slack的模板有几个问题。第一个问题是重复扫描。每次增广失败、调整顶标后很多模板会清空vis数组重新从起点执行DFS。这意味着起点以及之前已经访问过的左点它们的出边会被再次扫描。即使使用slack数组缓存了松弛量也仍然需要重新走一遍递归树很多重复计算隐藏在这层“递归回溯”里。第二个问题是递归栈。max权匹配的增广路最长可能达到nDFS递归深度也会达到n。在n2000的稠密图上即使没有爆栈大量递归调用本身也带来不小的常数。第三个问题是更新slack时全量遍历。调整顶标后要遍历一次所有未访问右点做slack[j] - delta这是O(n)的。单看还好但一轮增广可能调整多次累积起来也不小。所以我一直觉得传统DFS加slack只是“能过的O(n^3)”离“最优实现”还有距离。下面要讲的BFS迭代写法核心思路是让每个左点只被扫描一次并且完全去掉递归。3. 更快的优化BFS迭代版KM算法3.1 核心改进点解析我把这套更快写法称为BFS迭代版本质还是slack优化但实现细节完全不同。传统DFS的问题在于增广失败后为了继续找增广路必须递归回溯并重新搜索。而BFS版把每个左点放进队列从左往右逐层扩展。每个已访问的左点只出队一次只扫描它的出边一次没有重复劳动。同时slack数组维护的含义不变仍然是“树内左点到未访问右点的最小松弛量”。但BFS版不依赖递归而是通过一个明确的循环反复执行两个动作从队列中取出左点用它的出边更新slack和pre查找最小的slack调整顶标再把新暴露的匹配左点入队整个过程更像是在“走路”而不是在“递归回溯”。另一个重要的改进是pre数组的使用。在DFS版里pre通常用于记录slack更新来源在BFS版里pre同样是记录“某个右点当前最小松弛量来自哪个左点”。找到未匹配右点后沿着pre链就能还原整条增广路。3.2 BFS版增广流程详解拿一次增广举例。假设当前要给左点st找匹配。第一步初始化。清空visx、visy把slack全部置INFpre重置为空队列里放入st标记visx[st]true。第二步扩展队列。只要队列不为空就取出队首左点x枚举所有未访问右点y计算gapgap lx[x] ly[y] - w[x][y]如果gap比slack[y]小就更新slack[y]同时设置pre[y]x。第三步找最小松弛量。在所有未访问右点中选出slack[j]最小的那个记为y同时得到delta。第四步如果delta大于0就调整顶标S内左点 lx - delta T内右点 ly delta 未访问右点 slack - delta注意这一步不会破坏slack数组的累积含义因为所有未访问右点的slack都统一减少了delta。调整之后刚选中的y因为松弛量为0变成了一条新增的相等边。第五步标记y为已访问。如果y还没有匹配说明找到了一个未匹配右点增广路到此为止沿pre链回溯并翻转匹配即可。如果y已经匹配了左点x2那么把x2入队标记visx[x2]true继续下一轮扩展。这个流程中每个左点最多入队一次每个右点也最多被访问一次。每次处理完队列后查找delta需要扫描所有右点O(n)。整个增广过程最多扩展n个左点所以单次增广是O(n^2)总共n次增广复杂度O(n^3)。虽然理论复杂度没变但常数比DFS版小得多。3.3 可直接使用的C实现下面是我常驻的一套BFS版KM实现n是点数1-index权值矩阵用w[i][j]存。这里假设左右点数相等且一定有完美匹配实际工程中如果点数不等或者可能不满需要先补点补边。#include bits/stdc.h using namespace std; const long long INF 1e18; const int N 2005; long long w[N][N], lx[N], ly[N], slack[N]; int matchx[N], matchy[N], pre[N]; bool visx[N], visy[N]; bool bfs(int st, int n) { queueint q; while (!q.empty()) q.pop(); fill(visx 1, visx n 1, false); fill(visy 1, visy n 1, false); fill(slack 1, slack n 1, INF); fill(pre 1, pre n 1, 0); q.push(st); visx[st] true; while (true) { while (!q.empty()) { int x q.front(); q.pop(); for (int y 1; y n; y) { if (visy[y]) continue; long long gap lx[x] ly[y] - w[x][y]; if (gap slack[y]) { slack[y] gap; pre[y] x; } } } int y -1; long long delta INF; for (int j 1; j n; j) { if (!visy[j] slack[j] delta) { delta slack[j]; y j; } } if (delta 0) { for (int i 1; i n; i) { if (visx[i]) lx[i] - delta; if (visy[i]) ly[i] delta; } for (int j 1; j n; j) { if (!visy[j]) slack[j] - delta; } } visy[y] true; int x matchy[y]; if (x -1) { // 找到未匹配右点沿pre链翻转 while (y ! -1) { int px pre[y]; int ny matchx[px]; matchx[px] y; matchy[y] px; y ny; } return true; } else { visx[x] true; q.push(x); } } } long long km(int n) { fill(matchx 1, matchx n 1, -1); fill(matchy 1, matchy n 1, -1); fill(ly 1, ly n 1, 0); 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]); } } for (int i 1; i n; i) { bfs(i, n); } long long ans 0; for (int i 1; i n; i) { ans w[i][matchx[i]]; } return ans; }这个实现里有一点需要特别注意matchx[i]表示左点i匹配的右点初始为-1matchy[j]表示右点j匹配的左点初始也为-1。在bfs函数里找到未匹配右点后回溯沿pre链走到最后一个左点时matchx[px]一定是-1此时把ny置为-1循环自然结束。这里用-1而不是0能让逻辑更清晰但同时要求所有数组初始化时都统一用-1。还有一点在回溯翻转时pre[y]记录的左点一定是已经在交错树里的左点。比如根节点st它最初没有匹配所以当某个右点通过st的边被更新slack时pre[y]会等于st。翻转时先让st匹配上这个右点再顺着原来的匹配关系继续替换直到遇到某个原本没有匹配的左点。4. 复杂度对比和实测差距4.1 理论上为什么BFS更快先明确复杂度朴素实现O(n^4)每次找delta都枚举S和T外的所有组合。DFS加slackO(n^3)用slack数组缓存松弛量。BFS版本O(n^3)但常数明显更小。理论复杂度和DFS版相同为什么实际更快关键在于重复扫描次数。DFS版的一次增广如果第一次DFS失败调整顶标的完整过程是这样的先把slack更新一遍再清空vis重新从起点DFS。第二次DFS会再次把起点以及之前已经访问过的左点的出边扫描一遍。虽然slack数组保住了松弛量但扫描出边的开销重复发生了。如果一轮增广中调整了多次顶标重复扫描的次数会等比放大。BFS版不会这样。每个左点入队后它的出边只会被扫描一次之后无论调整多少次顶标都不会再重扫这个左点。整个一轮增广中每个左点最多入队一次扫描量是O(n^2)而不是“调整次数乘以n^2”。这在实际稠密图里带来的提升非常明显。另外BFS版没有递归函数不存在递归栈顶爆掉的问题也省去了大量函数调用开销。对于n1000以上的图这两点叠加起来运行时间往往能差出好几倍。4.2 一组实际压力测试我用随机的稠密图做过几组对比测试数据是完全二分图边权随机生成机器是普通台式机不涉及任何特定平台。为了公平两种实现都开了O2优化DFS版的递归深度足够不会爆栈。在n500时DFS加slack大约需要0.8秒BFS版本大约0.3秒。n1000时DFS版已经接近2秒BFS版本不到0.7秒。到n2000时DFS版跑到了7秒开外BFS版本还能压在2.5秒左右。这个差距会随着n增长继续扩大主要就是重复扫描和递归调用堆出来的常数。当然这不是说DFS版毫无价值。DFS版代码结构更简单适合在n比较小、或者比赛时间不紧的时候快速敲出来。但如果你的场景是n超过1000的稠密图BFS版本非常值得常驻在模板库中。4.3 是不是越复杂越“吊打”标题里用了“吊打”说实话有点标题党。BFS版本本质上还是slack优化只是把实现方式从递归换成迭代减少了重复扩展。它并没有改变O(n^3)的上界。我也见过有人在此基础上再用堆或线段树查最小slack想进一步压缩查找delta的O(n)扫描。这里要泼一盆冷水在完全稠密图里每个左点入队后仍然要扫描n条出边更新slack所以每轮增广的扫描量至少是O(n^2)。堆优化能把查delta从O(n)降到O(log n)但更新slack时每条边仍要push总复杂度会变成O(n^3 log n)理论反而更差。实测下来堆优化在n不大时稍微快一点点n大了以后经常比线性扫描慢。所以我不建议盲目上堆。真正值得投入时间的是BFS加slack数组、pre回溯、尽可能减少fill次数的这套写法。它已经是工程上很均衡的方案。5. 常见问题和避坑实录5.1 slack数组不初始化的后果很多新手把DFS模板改成BFS时会忘记在每轮增广前把slack数组初始化成INF。这样上一轮残留的松弛量会影响本轮判断可能让delta算出一个错误的小值导致顶标调整不足相等子图没有真正扩大。我通常会在bfs函数开头一次性reset五样东西visx、visy、slack、pre、队列。虽然初始化也是O(n)但相比整个增广过程微不足道。千万别为了省一点memset时间而省略初始化一旦出bug非常难查。5.2 回溯pre链时最容易写错pre数组的含义是“右点j当前最小松弛量由哪个左点产生”不是“交错树中右点的前一个右点”。有些人会把它和普通匈牙利算法的match路径搞混导致回溯时乱套。正确的回溯方式是这样从最终找到的未匹配右点y开始找到产生它的左点px这个左点原本匹配的右点是ny然后让px匹配yy匹配px接着把y更新为ny继续。每一步都是“右点向前找左点左点再换右点”直到遇到某个左点原本没有匹配。如果pre记录错了翻转出来的匹配会不合法甚至死循环。建议写完以后用一个3到4个点的小数据手工推一遍。5.3 非方阵图和缺失边怎么处理KM算法要求左右点数相等而且通常默认一定存在完美匹配。如果你的实际输入左右点数不等或者有些边不存在需要先补一个完整图。左右点数不等时在点数较少的一侧补虚拟点让两边都是n个点。缺失的边补成0权边。这样跑出来的匹配如果包含了虚拟边说明实际没有完美匹配需要业务层自己判断。注意补0权边适用于“最大权匹配不要求完美”的场景你希望尽量选高收益边那么0边可以让那些本来不该匹配的虚拟配对不增加总收益。但如果原始边权本身有负值并且你希望完美匹配里避开负边直接把缺失边补成0还不够更稳妥的做法是先把所有边权平移确保没有负权或者改用费用流。负权边的问题本质上是KM的顶标初始化方式决定的lx初始取每行最大值ly初始为0。如果某行全是负权lx会变成负数虽然仍然可行但相等子图里可能不存在任何边算法会一直在调整顶标。处理这类情况时我建议先把边权做一次整体平移让最小边权变成0再跑KM。5.4 浮点权值下的精度陷阱KM算法依赖“相等”这个强判断。如果边权是浮点数lx[i]ly[j]-w[i][j]因为浮点误差很难精确等于0。这时需要给gap判断加一个EPS通常取1e-9或1e-10认为绝对值小于EPS就算相等。但即使加了EPS浮点KM也比较脆弱因为delta的更新和slack的累积会不断放大误差。如果非用不可建议统一用long double并把所有非零判断都改成与EPS比较。如果图比较稀疏或者边权是浮点数但数据量不大我个人更推荐用最小费用最大流来求最大权匹配它不会因为精度问题陷入死循环。5.5 如何判断不存在完美匹配KM并不能直接告诉你“匹配不存在”。当算法跑完全部左点某些左点仍然没有匹配时就是不存在完美匹配。这时候matchx里会有-1。更早的判断方法是先跑一遍不带权的匈牙利算法看看最大匹配数是否等于n。如果不是n直接放弃KM。这个预检是O(n^3)但常数很小能帮你避免在KM里调顶标调出问题。另外补虚拟点时也要注意。如果原始图有个左点孤立无邻边补0边后它可能会匹配到虚拟右点。业务层面要知道这个结果代表“没有人愿意接这个任务”而不是真实分配。5.6 时间戳优化要不要加BFS版本最耗时的其实是fill数组。如果你追求极致性能可以用时间戳替代visx、visy的fill操作用curTime的方式判断是否访问过。slack和pre依然要每轮重置。实际测试里时间戳优化能省一点fill时间但不会像从DFS换成BFS那样带来量级变化。我一般建议先把BFS版本写对再用性能分析工具看瓶颈在哪里。如果fill占比很高再上时间戳不迟。最后分享一个实用经验我最初写KM时也迷信DFS加slack就是最优解直到某次处理一个n1200的稠密图DFS版跑了很久还时不时抖动换成BFS版以后稳定了许多。后来再遇到类似分配问题我默认就会用BFS版这套模板。如果你正在给某个实际系统做排班或任务分配还有一个小建议不要一上来就KM。先确认数据规模。n在100以下朴素DFS都无所谓n到了几百上千再上KM。而且KM对完美匹配的要求很严格如果业务允许“有人闲着没任务”最好把模型改成允许虚拟匹配或者直接上费用流否则算法会在边界条件上吃掉你大量时间。希望这篇能帮你少走一些弯路。