企业官网建设流程全解析

写带权二分图匹配，KM算法是个绕不过去的名字。尤其是刚接触“工人-任务”这类分配问题时，很多人第一反应就是上KM：左侧是人，右侧是任务，边权是效率或收益，最后要的是一组完美匹配，让总收益最大。网上流传最广的模板是DFS加slack数组的写法，虽然已经比最原始的O(n^4)快了不少，但真扔到几千个点的稠密图上，还是能明显感觉到卡顿。这篇文章我会从KM算法的数学原理开始，逐步讲清楚传统slack优化为什么还不够快，再给出一套基于BFS迭代的更快写法，并用实际压力测试数据做对比。想彻底搞懂KM为什么能求出最大权匹配，以及怎么把常数压到最小，这篇应该能帮到你。

1. 先把KM的核心思想讲透

1.1 最大权完美匹配到底在求什么

先说问题定义。给定一个二分图，左部有n个点，右部有n个点，每条边有一个权值w[i][j]。要找一组匹配，让每个左点恰好匹配一个右点，每个右点也恰好匹配一个左点，这就是完美匹配。如果希望匹配中所有边的权值和最大，就叫最大权完美匹配。

最直观的做法是暴力枚举所有排列，n个点的排列数量是n!，n=10就受不了。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，这些点组成的树就是交错树。如果搜索失败，说明交错树中所有可达右点都已经匹配，没有再往外的路。

这时候计算一个关键值delta：

delta = min{ lx[i] + ly[j] - w[i][j] } 其中 i 属于 S，j 不属于 T

然后做一次顶标调整：

对于所有 i 属于 S：lx[i] -= delta 对于所有 j 属于 T：ly[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值也要统一减delta：

if (!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权匹配的增广路最长可能达到n，DFS递归深度也会达到n。在n=2000的稠密图上，即使没有爆栈，大量递归调用本身也带来不小的常数。

第三个问题是更新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全部置INF，pre重置为空，队列里放入st，标记visx[st]=true。

第二步，扩展队列。只要队列不为空，就取出队首左点x，枚举所有未访问右点y，计算gap：

gap = 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) { queue<int> 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匹配的右点，初始为-1；matchy[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加slack：O(n^3)，用slack数组缓存松弛量。
• BFS版本：O(n^3)，但常数明显更小。

理论复杂度和DFS版相同，为什么实际更快？关键在于重复扫描次数。

DFS版的一次增广，如果第一次DFS失败，调整顶标的完整过程是这样的：先把slack更新一遍，再清空vis，重新从起点DFS。第二次DFS会再次把起点以及之前已经访问过的左点的出边扫描一遍。虽然slack数组保住了松弛量，但扫描出边的开销重复发生了。如果一轮增广中调整了多次顶标，重复扫描的次数会等比放大。

BFS版不会这样。每个左点入队后，它的出边只会被扫描一次，之后无论调整多少次顶标，都不会再重扫这个左点。整个一轮增广中，每个左点最多入队一次，扫描量是O(n^2)，而不是“调整次数乘以n^2”。这在实际稠密图里带来的提升非常明显。

另外，BFS版没有递归函数，不存在递归栈顶爆掉的问题，也省去了大量函数调用开销。对于n=1000以上的图，这两点叠加起来，运行时间往往能差出好几倍。

4.2 一组实际压力测试

我用随机的稠密图做过几组对比，测试数据是完全二分图，边权随机生成，机器是普通台式机，不涉及任何特定平台。为了公平，两种实现都开了O2优化，DFS版的递归深度足够，不会爆栈。

在n=500时，DFS加slack大约需要0.8秒，BFS版本大约0.3秒。n=1000时，DFS版已经接近2秒，BFS版本不到0.7秒。到n=2000时，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匹配y，y匹配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就是最优解，直到某次处理一个n=1200的稠密图，DFS版跑了很久还时不时抖动，换成BFS版以后稳定了许多。后来再遇到类似分配问题，我默认就会用BFS版这套模板。

如果你正在给某个实际系统做排班或任务分配，还有一个小建议：不要一上来就KM。先确认数据规模。n在100以下，朴素DFS都无所谓；n到了几百上千，再上KM。而且KM对完美匹配的要求很严格，如果业务允许“有人闲着没任务”，最好把模型改成允许虚拟匹配，或者直接上费用流，否则算法会在边界条件上吃掉你大量时间。希望这篇能帮你少走一些弯路。