KM算法适用于左右点数相等且存在完美匹配的带权二分图最大权匹配场景，如任务分配、资源调度、多目标跟踪等；要求初始化顶标lx[i]=max(wi)、ly[j]=0，并通过调整顶标在相等子图中寻找增广路。
KM算法在C++中适用于什么场景
KM（Kuhn-Munkres）算法只适用于**完备匹配存在前提下的带权二分图最大权匹配**，也就是左右部点数相等（n == m），且要求存在一个完美匹配。如果你的图不满足这点（比如左右点数不等、或某些点注定无法全部匹配），直接套KM会失败或得到错误结果——它不会自动补零或删边，而是依赖你预设的“虚拟点+极大负权重”等人工处理。
常见误用场景包括：任务分配问题中工人数≠任务数、稀疏图强行填满邻接矩阵、未初始化顶标导致死循环。
核心数据结构和初始化要点
KM算法本质是通过不断调整左右部顶点的顶标（lx[]、ly[]）来维持相等子图，并用DFS/BFS找增广路。关键不是“怎么写DFS”，而是“顶标怎么设才合法”。初始时必须满足：lx[i] = max(weight[i][j]) 对所有 j，ly[j] = 0。否则后续的 lx[i] + ly[j] >= weight[i][j] 不成立，算法直接崩溃。
-
weight[i][j]必须是整数或浮点数，但建议统一用int避免浮点误差；若原图是求最小权匹配，统一用INF - weight[i][j]转为最大权问题 - 邻接矩阵大小至少为
[n][n]，即使实际右部只有m 个有效点，也要把多余列填为 <code>-INF（不能是0！否则会被误认为可匹配） - 每次DFS前要清空
visx[]、visy[]和pre[]（记录交错路径的前驱），漏清会导致上一轮状态污染
DFS增广与顶标更新的临界判断
标准KM的DFS返回值是“是否找到增广路”，但真正容易出错的是**顶标更新逻辑**：当DFS失败时，需计算所有未访问左点 i 与已访问右点 j 的松弛量 slack[j] = min(lx[i] + ly[j] - weight[i][j])，再用 delta = min(slack[j]) 同时调整顶标——lx[i] -= delta（对已访问左点），ly[j] += delta（对已访问右点）。漏掉任一方向，相等子图就失衡。
立即学习“C++免费学习笔记（深入）”；
常见错误：
- 把
delta错算成min(lx[i] + ly[j] - weight[i][j])对所有i,j—— 这会破坏顶标性质 - 更新时只改
ly[]忘了lx[]，导致后续lx[i] + ly[j]整体偏大，再也进不了相等子图 - 使用邻接表时没维护
slack[]数组，每次DFS都重新扫全图，时间退化到O(n^4)
完整可运行片段的关键粘合点
下面这段不是教学模板，而是你调试时最需要核对的三处：
int match[105], lx[105], ly[105], slack[105];
bool visx[105], visy[105];
int pre[105]; // BFS版常用，DFS版也可用作记录增广路径
<p>// 初始化顶标
for (int i = 1; i <= n; i++) {
lx[i] = -0x3f3f3f3f;
for (int j = 1; j <= n; j++)
lx[i] = max(lx[i], weight[i][j]);
}
memset(ly, 0, sizeof ly);</p><p>// DFS主体（匈牙利风格）
bool dfs(int x) {
visx[x] = true;
for (int y = 1; y <= n; y++) {
if (visy[y]) continue;
int t = lx[x] + ly[y] - weight[x][y];
if (t == 0) {
visy[y] = true;
if (!match[y] || dfs(match[y])) {
match[y] = x;
return true;
}
} else slack[y] = min(slack[y], t);
}
return false;
}</p><p>// 主循环
for (int x = 1; x <= n; x++) {
memset(visx, 0, sizeof visx);
memset(visy, 0, sizeof visy);
fill(slack + 1, slack + n + 1, 0x3f3f3f3f); // 关键：每次重置 slack
while (!dfs(x)) {
int delta = 0x3f3f3f3f;
for (int j = 1; j <= n; j++)
if (!visy[j]) delta = min(delta, slack[j]);
for (int i = 1; i <= n; i++) {
if (visx[i]) lx[i] -= delta;
if (visy[i]) ly[i] += delta;
}
memset(visx, 0, sizeof visx);
memset(visy, 0, sizeof visy);
}
}</p>注意 slack 数组必须在每次 dfs() 前重置为极大值，且 delta 只从未访问的 y 中取最小——这里错一点，整个匹配就崩。
