企业官网建设流程全解析

我第一次正式用KM算法，是在调一个任务分配的模拟模型：十几个人、十几个任务，各自有一个收益矩阵，要求每个人恰好分到一个任务，且总收益最大。当时网上搜到的KM模板清一色是DFS递归加slack数组的写法，看起来逻辑严密，但把数据规模加到几百之后，运行时间就肉眼可见地不对劲。进一步排查才发现，时间复杂度虽然写着O(n^3)，但DFS那套“调整顶标后清空vis、重新递归”的做法，在权值分布不均匀时会带来大量重复搜索，常数大到让人怀疑算法本身。这篇文章就把KM算法从原理到实现彻底拆开，重点讲清楚我最后采用的BFS+pre数组重构方案，以及为什么它比传统的slack优化写法更适合实际场景。

1. 二分图最大权完美匹配：KM算法在解决什么问题

1.1 问题定义与建模方式

KM算法解决的是二分图最大权完美匹配问题。形式化地说，给定左部点集L和右部点集R，|L|=|R|=n，每条边L_i到R_j有一个权值w[i][j]，要求找出一个一一映射f: L→R，使得所有匹配边的权值之和最大。这个“一一映射”就是完美匹配。

实际建模中非常常见的场景是指派问题。比如n个工人分配给n个任务，矩阵里存的是第i个工人完成第j个任务的效率或收益；又比如特征点关联、两个集合之间的最佳对应关系。只要问题能写成“左右两边数量相等、要一一配对、边有权值要最大化总和”，就可以直接套KM。

如果左右两边数量不相等，通常做法是把数量少的一侧补几个假点，让两侧都变成同一个规模n。补出来的假点与另一侧所有点的连边权值设为0。注意这里有个分岔口：如果题目要求的是“完美匹配”（也就是所有真实点都必须匹配），那么假点之间的0边可以接受；如果题目只要求“最大权匹配”而不要求所有点匹配，那补0边的做法也成立，因为0权边不会让答案变差。反过来，如果题目的完美匹配中不允许某些边存在，那么这些边要补成一个负的极大值（如-1e15），而不是0，否则算法会优先选不存在边导致答案错误。这个细节我在后面还会单独强调。

1.2 为什么KM算法比费用流更适合这类问题

有些人会把最大权完美匹配转化成最小费用最大流，从建模的通用性上看费用流肯定更灵活，但KM在完全二分图上的优势非常明显：经典实现O(n^3)，而费用流在完全图上每轮增广都可能扫大量边，实际表现往往差一个量级。再加上KM代码更短、无堆栈压力，所以只要题目保证是完全二分图，KM基本就是最优选。

另一种常见误区是直接对矩阵做匈牙利算法求最大匹配，再按匹配边权求和。匈牙利算法只能处理无权图，不能直接替代KM。KM的核心是引入了“顶标”机制，把带权匹配问题转化成对相等子图做无权增广，这一点是理解后续所有优化的钥匙。

2. 顶标与相等子图：KM算法的数学基础

2.1 可行顶标是什么

为每个左部点维护一个值lx[i]，为每个右部点维护一个值ly[j]，满足对于所有边(i,j)都有：

lx[i] + ly[j] >= w[i][j]

这样的lx和ly就称为一组可行顶标。一个最简单的可行顶标构造方式是：ly全部置0，lx[i]取矩阵第i行的最大值。因为每行最大值加上0一定不小于该行任意一个w[i][j]，所以可行性成立。

KM算法的全部过程，都是在这组可行顶标的约束下进行的，任何时候都不能打破这个不等式。

2.2 相等子图与核心定理

把满足下面等式的边保留下来，构成的子图叫相等子图：

lx[i] + ly[j] == w[i][j]

核心定理是：如果当前相等子图中存在一个完美匹配，那么这个匹配就是原图上的最大权完美匹配。

证明思路很短。取任意一个完美匹配M'，因为每条边都满足lx[i] + ly[j] >= w[i][j]，所以M'的总权值不超过所有顶标之和，也就是：

sum_{(i,j) in M'} w[i][j] <= sum_i lx[i] + sum_j ly[j]

再看相等子图里的完美匹配M，它的每条边都满足等号，因此：

sum_{(i,j) in M} w[i][j] = sum_i lx[i] + sum_j ly[j]

所以相等子图里的完美匹配M必然是最优的。这个证明非常干净，也说明KM算法的本质是：不断调整顶标，让相等子图逐渐扩大，直到相等子图里能找到一个完整匹配。

2.3 顶标调整的直观理解

顶标调整的过程可以理解为双方讨价还价。左部点是“报价方”，右部点是“要价方”，只有当lx[i]+ly[j]恰好等于w[i][j]时才谈得拢。某个左部点尝试匹配时发现没有合适的右部点，说明它需要“加价”或者让对方“降价”。而KM的做法是：所有已经参与谈判的左部点统一降低lx，所有已经参与谈判的右部点统一提高ly，两者之和保持不变，因此已有的相等边不会丢失；同时，因为左部点lx降低了，原来略低于达成条件的边现在差值变小，其中有最小差值的边就会率先进入相等子图。反复这个过程，相等子图的边就会越来越多。

这一小节理解透了，后续不管DFS还是BFS实现，都只是在这个规则上做搜索策略的差别而已。

3. 经典DFS+slack写法：一个O(n^3)但容易慢的实现

3.1 传统写法与slack数组的含义

不加任何优化的KM朴素做法，每次调整顶标都需要在“已访问左部点集合”和“未访问右部点集合”之间暴力扫描所有边，求最小差值，单次增广最坏就是O(n^3)，整体O(n^4)。为了压到O(n^3)，经典做法引入slack数组。

slack[j]表示：在当前这一轮增广中，所有已访问的左部点i到未访问右部点j的差值lx[i]+ly[j]-w[i][j]中的最小值。有了它，求全局最小delta时只需要扫一遍右部点，扫完得到最小delta后，所有未访问右部点的slack[j]统一减去delta，就能在O(n)时间内完成顶标调整。

下面这段是网上最常见的DFS实现，我把结构完整写出来，作为后文对比的基准：

vector<int> lx, ly, matchL, matchR; vector<int> slack; vector<char> visL, visR; int n; bool dfs(int u) { visL[u] = 1; for (int v = 0; v < n; v++) { if (visR[v]) continue; int gap = lx[u] + ly[v] - w[u][v]; if (gap == 0) { visR[v] = 1; if (matchR[v] == -1 || dfs(matchR[v])) { matchL[u] = v; matchR[v] = u; return true; } } else { slack[v] = min(slack[v], gap); } } return false; } void KM() { lx.assign(n, 0); ly.assign(n, 0); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) lx[i] = max(lx[i], w[i][j]); matchL.assign(n, -1); matchR.assign(n, -1); for (int u = 0; u < n; u++) { slack.assign(n, INF); while (true) { visL.assign(n, 0); visR.assign(n, 0); if (dfs(u)) break; int delta = INF; for (int j = 0; j < n; j++) if (!visR[j]) delta = min(delta, slack[j]); for (int i = 0; i < n; i++) if (visL[i]) lx[i] -= delta; for (int j = 0; j < n; j++) if (visR[j]) ly[j] += delta; for (int j = 0; j < n; j++) if (!visR[j]) slack[j] -= delta; } } }

这段代码在n=300以内的数据上通常表现不错，这也是它长期是“标准模板”的原因。

3.2 复杂度分析的正确姿势

从理论上讲，每个左部点u在最坏情况下会被多次尝试增广，但每一次增广过程中，每个左部点最多被访问一次，每个右部点最多被访问一次。每个左部点被访问时会扫描n个右部点并更新slack，所以单次增广的搜索开销是O(n^2)。调整顶标的次数最多是n次，每次调整扫描右部点O(n)。所以单个左部点的增广是O(n^2+n^2)，摊到n个左部点身上就是O(n^3)。这个渐进结论本身没有问题。

问题恰恰出在“最多被访问一次”这个理论上成立、实际却因为递归结构导致反复进入的判断上。

3.3 为什么理论O(n^3)实际却慢

DFS版本每调整一次顶标后，都要在while循环里清空visL和visR，然后从当前根u重新开始递归。想一想这个过程：第一次从根u出发，递归到某棵交错树，访问了几个左部点和右部点，发现找不到增广路；然后调整delta，第二次又从根u出发，重新递归进入之前已经访问过的左部点。这些节点明明已经被确认无法直接匹配，但因为vis数组被清空了，它们必须再被完整地扫描一遍。如果一组顶标的调整需要多次delta才能解锁目标右部点，那么这些重复扫描会被反复执行。

在权值呈现“平台化”分布时，比如大量的w都集中在一个较小的数值区间，不同边的gap值经常相同，往往很多边的gap等于同一个delta。这样每次调整只能解锁少数几条边，需要多次调整顶标，重复搜索的次数会明显增加。实测中这种数据下DFS版本的递归深度和函数调用次数都很大，常数非常难看。

4. 更快方向：BFS+pre数组重构，真正更快的KM写法

4.1 BFS重构解决的核心问题

既然DFS的瓶颈在于“调整顶标后清空vis重新递归”，那自然的改进方向是：不要让已访问状态丢失，顶点标调整后继续从断点往下走。BFS+pre数组的做法就是为此设计的。

具体来说，用队列维护当前待扩展的左部点。左部点u进入队列后，立即扫描它到所有未访问右部点的边，更新slack和pre。其中pre[j]记录“当前是哪个左部点让右部点j的slack达到最小值”，也就是增广路径中右部点j的前驱左部点。当某个右部点j的slack变成0，意味着它在相等子图中可以被当前已访问左部点集合直接到达。这时视情况处理：如果j未匹配，那么找到了一条增广路，记录foundRight；如果j已经匹配给左部点p，就把p也入队，让它继续扩展。这就是对相等子图的BFS扩展。

顶标调整时，仍然找所有未访问右部点的最小slack作为delta，然后更新lx、ly和slack。关键是，已经访问的左部点和右部点都保留在vis数组里，不会因为调整delta而丢失。同时，因为slack[j]统一减delta，一旦某个未访问右部点slack变成0，它会立刻被挂到已访问集合中，并立即触发后续处理。一次顶标调整可能解锁多个右部点，相比于DFS一次递归只处理一个分支，BFS版本的扩展效率更高。

4.2 完整可运行代码

下面是我目前手头最常用的BFS版本，完整可以直接用，适合稠密完全图，边权保存在n×n矩阵里。

#include <bits/stdc++.h> using namespace std; const int INF = 1e9; struct KM { int n; vector<vector<int>> w; vector<int> lx, ly, matchL, matchR; KM(int n_, const vector<vector<int>>& w_) : n(n_), w(w_) { lx.assign(n, 0); ly.assign(n, 0); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) lx[i] = max(lx[i], w[i][j]); matchL.assign(n, -1); matchR.assign(n, -1); } int solve() { for (int root = 0; root < n; root++) { vector<int> slack(n, INF); vector<int> pre(n, -1); vector<char> visL(n, 0), visR(n, 0); queue<int> q; q.push(root); visL[root] = 1; int foundRight = -1; while (foundRight == -1) { while (!q.empty() && foundRight == -1) { int i = q.front(); q.pop(); for (int j = 0; j < n; j++) { if (visR[j]) continue; int gap = lx[i] + ly[j] - w[i][j]; if (gap < slack[j]) { slack[j] = gap; pre[j] = i; } if (slack[j] == 0) { visR[j] = 1; if (matchR[j] == -1) { foundRight = j; break; } int nxtLeft = matchR[j]; if (!visL[nxtLeft]) { visL[nxtLeft] = 1; q.push(nxtLeft); } } } } if (foundRight != -1) break; int delta = INF; for (int j = 0; j < n; j++) if (!visR[j]) delta = min(delta, slack[j]); for (int i = 0; i < n; i++) if (visL[i]) lx[i] -= delta; for (int j = 0; j < n; j++) if (visR[j]) ly[j] += delta; for (int j = 0; j < n; j++) { if (visR[j]) continue; slack[j] -= delta; if (slack[j] == 0) { visR[j] = 1; if (matchR[j] == -1) { foundRight = j; break; } int nxtLeft = matchR[j]; if (!visL[nxtLeft]) { visL[nxtLeft] = 1; q.push(nxtLeft); } } } } int curRight = foundRight; while (curRight != -1) { int leftPoint = pre[curRight]; int prevRight = matchL[leftPoint]; matchL[leftPoint] = curRight; matchR[curRight] = leftPoint; curRight = prevRight; } } int ans = 0; for (int i = 0; i < n; i++) ans += w[i][matchL[i]]; return ans; } };

4.3 代码逐段拆解

先看BFS扩展部分。队列里存的是左部点。初始时根节点root入队，之后每遇到一个已匹配右部点j，就把它的匹配左部点matchR[j]也入队。这意味着相等子图里的交错的“左右左”路径正在向外扩展。之所以用队列而不是直接递归，是因为我们希望在delta调整后，队列里的节点可以紧接着继续处理，而不是像DFS那样从根重新来过。

每个左部点i出队时，扫描所有未访问右部点j，计算gap。如果gap比slack[j]更小，就更新slack[j]，并记录pre[j]=i。pre数组非常关键，它保存了当前使右部点j“最有可能”进入相等子图的左部点。注意这里不是所有能到达j的左部点都记录，只记录让gap最小的那个。当slack[j]==0时，说明从某个已访问左部点出发，有一条相等边可以到达j，这时j在相等子图中是可达的。

如果可达的j未匹配，增广路就找到了，foundRight被赋值为j，可以立即跳出循环。如果j已匹配，则j的配偶左部点入队继续扩展BFS。这相当于一条交替路径：左点i到达右点j，j的匹配左点p继续向前尝试。由于BFS的性质，第一次遇到未匹配右部点时，经由pre数组回溯得到的路径一定是一条增广路径。

顶标调整部分在队列清空但没有找到未匹配右部点时执行。此时已访问左部点们的所有相等边都试探过了，无法继续扩展，只能放宽条件让新的边进入相等子图。delta取所有未访问右部点slack的最小值。这个delta的来源是：在所有“已访问左部点”到“未访问右部点”的边中，最接近相等条件的那个差值。调整lx和ly后，已经处于相等子图的边不会丢失，这一点在原理部分讲过，代码里也能验证。

之后更新未访问右部点的slack[j] -= delta，再检查哪些右部点slack变为0，这些点就是刚刚进入相等子图的点。它们和BFS过程中遇到slack==0的点一样，要统一走“未匹配则收网，已匹配则入队”的逻辑。

最后是增广路径的翻转。通过pre数组从foundRight一路回溯。举个例子，假设pre[foundRight]=a，那么右部点foundRight将被匹配给左部点a；而a原来匹配的右部点b会被释放；再看pre[b]=c，那么b将匹配给c，c原来匹配的右部点d被释放……如此循环，直到某个左部点的原匹配右部点是-1为止。这个过程中每个匹配只被更新一次，整条路径翻转正确。

4.4 为什么这个版本的复杂度稳定在O(n^3)

在BFS版本里，每个左部点在整个增广过程中最多入队一次，每个右部点最多被标记一次。某一个左部点出队时扫描n个右部点，所以所有左部点出队扫描的累计代价是O(n^2)。delta调整的次数也受限于右部点的数量，每次调整至少会让一个未访问右部点的slack变成0并被标记为已访问，所以最多n次调整，每次调整扫描右部点数组O(n)，累计O(n^2)。因此单个左部点的增广代价是O(n^2)，n个左部点就是O(n^3)。

更重要的是，这个复杂度的常数非常稳定。因为vis数组不会被清空，pre和slack也不需要反复重算，已经做过的工作不会因为顶标调整而作废。遇到前面说的“平台化权值”数据时，BFS版本仍然保持一套流程走完，不会出现DFS那种反复从根递归的退化情况。这也是我称它能“更稳定更快”的原因。

5. 堆优化和稀疏图：一个需要冷静看待的方向

5.1 常见的堆优化思路

有些人在传统slack数组的基础上，想进一步用优先队列维护所有未访问右部点的最小slack，这样每次求delta就不需要扫描O(n)的数组，直接取堆顶就行。每次访问新的左部点时，把改善后的gap值push进堆，配合懒惰删除来解决过期旧值问题。这听起来很合理，在一些博客里也被包装成“比slack更快的优化”。

但实际用下来我得说，这个方向没有宣传的那么美好。KM不同于普通的贪心，顶标调整时所有未访问右部点的slack会统一减少一个delta，这种“全局减”的操作对堆来说是非常不友好的。

5.2 全局减delta导致堆失效的坑

考虑一个已经push进堆里的记录(value, j)，value对应的是某次更新后右部点j的slack值。顶标调整后，j作为未访问右部点，它的slack实际变成了value - delta。也就是说，堆里存的值和变量slack[j]的真实值之间出现了差值。懒惰删除常用的判断方式是“取堆顶时如果value != slack[j]就淘汰”，但在全局减delta的过程中，旧的堆顶value永远大于slack[j]，所有旧记录都处于“看似过期”的状态，于是堆里全是无效数据。

一种补救办法是维护全局偏移量。每调整一次delta，就把偏移量累加，slack[j]的真实值可以表示为“堆中存储值减去偏移量”。这样判断堆顶记录是否有效时需要用真实值比对。但问题在于，当一个右部点从“未访问”变成“已访问”时，偏移量对它失效；当它被某个新左部点更新gap时，又要把偏移量的影响折算进新push的记录里。各种状态切换让代码变得相当繁琐，稍有疏忽就出错。

更重要的是，就算实现了，也只是把求delta的O(n)降低成了O(log n)，但每个左部点出队时仍然要扫描n个右部点更新slack，整体复杂度反而可能变成O(n^3 log n)，比BFS版本的常数O(n^3)更差。堆优化真正的适用场景是稀疏图，比如每个左部点只有几十条边，这时候扫描邻接表的代价远低于扫描n个右部点。可一旦图稀疏到那个程度，KM本身的矩阵式更新也未必划算。

5.3 稀疏图该不该用KM

我的建议是：完全二分图、稠密图优先用上面的BFS矩阵版KM；如果图稀疏，匹配关系不是“所有点都要两两配对”这种强约束，直接转最小费用最大流会更省心。费用流可以写成增广路形式，每次用最短路过一次，实际边数少时效率很高，也不用处理一堆补边、负边、完美匹配是否存在的边界问题。

如果题目强制要求稀疏图跑KM，比如边数m比n^2小一个量级，且n又不算太大，可以考虑用邻接表存储边，并把顶标调整的delta计算仍然放在右部点数组上。这时每轮访问左部点只遍历它的邻接边，可以节约一部分无效扫描，但面对“未访问右部点数组”这一层O(n)的更新，总体理论复杂度依旧没有本质改善，只是工程上常数好一点。要明确一个事实：KM算法为了维护“所有右部点都可能成为匹配目标”，天然要经常检查全部右部点，稀疏带来的红利很有限。

6. 工程向加速技巧：从模板到真正能打

6.1 贪心初始化，减少增广轮数

BFS版本严格按顺序对每个左部点做一次增广，但很多左部点在初始状态下就能直接匹配。在主循环之前，可以先把能直接匹配的点处理掉，减少后续增广次数。具体做法是：初始化lx[i]为第i行最大值，ly全0，把所有点放进一个“待处理集合”；遍历左部点，如果存在一条满足lx[i]+ly[j]==w[i][j]且右部点j未匹配的边，就直接令matchL[i]=j、matchR[j]=i，跳过对该点的完整KM增广。

这个贪心不会破坏可行性，因为匹配边全部在相等子图内，且顶标仍然保持可行。对随机权值数据，能直接在初始相等子图里找到匹配的左部点比例不低，尤其是矩阵中出现较多大值时。实测下来，这个优化对大n数据的加速很可观，而且代码只要多加一个小函数，风险很低。需要注意的是，贪心匹配可能让某个右部点被某个左部点占住，而后续真正需要它的左部点只能走增广路径换走它，这会增加后续增广代价。所以更稳的做法是把左部点按“最大边权从大到小”排序后再贪心，优先满足最“挑剔”的点。

6.2 用时间戳替代vis数组清空

BFS版本每轮都要新建vector visL和visR，n在1000时其实无所谓，但n到了3000以上，vector的构造和清空成本也值得优化。一个常见技巧是用int数组和自增的时间戳标记：

vector<int> visL(n, 0), visR(n, 0); int stampL = 0, stampR = 0;

每轮增广时让stampL++、stampR++，检查visL[u]==stampL就表示本轮被访问过，赋值时直接写visL[u]=stampL。这样省掉了每轮重新fill数组的O(n)初始化，让BFS的常数进一步缩小。同理，slack和pre也可以用静态数组复用，但注意每轮增广开始时pre必须重置为-1，slack必须重置为INF，否则会残留上一轮的状态。时间戳只能优化vis，不能省掉这两个数组的清空，除非你愿意额外维护版本号，不过那得不偿失。

6.3 非完全图、负权和long long边界

非完全图处理前面提过。要求完美匹配时，不存在的边要补成极小数。建议使用类似于NEG_INF = -4e18（如果权值用long long）这样的值，并且注意在lx初始化时不要被NEG_INF干扰。更安全的做法是先判断边是否存在，不存在就跳过，而不是直接参与lx的计算。如果矩阵本身是稀疏的，用邻接表比补成大矩阵更合理。

负权的情况很多初学者会慌。其实KM的顶标初始化要求lx[i]至少等于该行的最大边权，无论这个最大边权是正是负，都满足lx[i]+ly[j]>=w[i][j]。所以负权不影响正确性，lx负值也可以正常运作。唯一要留意的是slack初始值要用足够大的INF，不能因为边权为负就把INF给盖掉。

边权很大或者求最小权匹配时取反的话，必须把代码里的int全部替换成long long。KM里最容易被忽略的就是INF和NEG_INF的选择，很多人就是挂在这里：INF太小，slack更新时被真实gap覆盖导致delta算错；或者NEG_INF不够小，与真实负边权混淆。我自己的习惯是，边权绝对值不超过1e9时，INF取4e18，NEG_INF取-4e18，完全不纠结。

6.4 数据规模与算法选择的经验判断

以我的经验来说，n在300以内，DFS版本和BFS版本差距不大，用哪个模板都可以；n到500以上，DFS版本的递归调用次数和常数劣势会明显暴露，BFS版本更稳；n到1000以上，BFS版本也建议配上6.1的贪心初始化；如果n超过3000且图是稠密的，那要先问自己数据是不是故意卡KM，很多时候换一种建模方式才是正解。

我在实际写KM时踩过几次坑之后，最大的体会就是：KM这类经典算法，网上模板虽然多，但它们往往只保证了渐进复杂度，真正的瓶颈埋藏在实现细节里。DFS+slack不是不能用，而是面对大规模数据时，它的重复递归搜索让O(n^3)的常数被无限放大；BFS+pre数组看起来只是把递归换成了队列，实际上是把“调整顶标后重新搜索”的隐含开销彻底消掉了。下次如果你发现自己手头的KM模板在大数据上卡成乌龟，别急着怀疑算法复杂度写错了，先把模板换成这套BFS版本，大概率立竿见影。