KM算法详解（C++语言实现二分图最大权匹配）

KM算法核心思想

KM算法通过维护两个顶标（label）数组 lx[] 和 ly[]，使得对于任意边 (i, j)，都有 lx[i] + ly[j] >= weight[i][j]。当等号成立时，这条边称为“可行边”。算法不断调整顶标，扩大相等子图，直到找到完美匹配。

关键点：

• 初始时，lx[i] = max(weight[i][j])，ly[j] = 0
• 使用类似匈牙利算法的 DFS/BFS 寻找增广路径
• 若找不到，则更新顶标，继续尝试

C++实现步骤详解

下面是一个完整的 KM 算法 C++ 实现。我们假设图是完全二分图（即左右点数相等，且任意两点间有权重）。

#include <iostream>#include <vector>#include <climits>#include <cstring>using namespace std;const int MAXN = 105; // 最大点数const int INF = 0x3f3f3f3f;int n; // 左右点数（假设相等）int weight[MAXN][MAXN]; // 权重矩阵int lx[MAXN], ly[MAXN]; // 顶标int match[MAXN]; // 右侧点匹配的左侧点bool vx[MAXN], vy[MAXN]; // 访问标记int slack[MAXN]; // slack[j] = min{lx[i] + ly[j] - weight[i][j]}// 尝试为左侧点 u 找到匹配bool dfs(int u) {    vx[u] = true;    for (int v = 0; v < n; ++v) {        if (vy[v]) continue;        int tmp = lx[u] + ly[v] - weight[u][v];        if (tmp == 0) {            vy[v] = true;            if (match[v] == -1 || dfs(match[v])) {                match[v] = u;                return true;            }        } else if (slack[v] > tmp) {            slack[v] = tmp;        }    }    return false;}// KM 主函数，返回最大权匹配值int KM() {    // 初始化顶标    memset(lx, 0, sizeof(lx));    memset(ly, 0, sizeof(ly));    for (int i = 0; i < n; ++i)        for (int j = 0; j < n; ++j)            lx[i] = max(lx[i], weight[i][j]);        // 初始化匹配    memset(match, -1, sizeof(match));        for (int i = 0; i < n; ++i) {        fill(slack, slack + n, INF);        while (true) {            memset(vx, false, sizeof(vx));            memset(vy, false, sizeof(vy));                        if (dfs(i)) break;                        // 更新顶标            int delta = INF;            for (int j = 0; j < n; ++j)                if (!vy[j]) delta = min(delta, slack[j]);                        for (int j = 0; j < n; ++j) {                if (vx[j]) lx[j] -= delta;                if (vy[j]) ly[j] += delta;                else slack[j] -= delta;            }        }    }        // 计算最大权值和    int result = 0;    for (int j = 0; j < n; ++j)        result += weight[match[j]][j];    return result;}int main() {    cin >> n;    for (int i = 0; i < n; ++i)        for (int j = 0; j < n; ++j)            cin >> weight[i][j];        cout << "最大权匹配值为: " << KM() << endl;    return 0;}

代码说明

• lx[] 和 ly[] 是左右两侧的顶标，保证 lx[i] + ly[j] >= weight[i][j]
• match[v] = u 表示右侧点 v 被匹配到左侧点 u
• slack[v] 记录当前最小的 lx[i] + ly[v] - weight[i][v]，用于快速更新顶标
• DFS 函数尝试为左侧点 u 找到增广路径

时间复杂度与应用场景

KM算法的时间复杂度为 O(n³)，适用于中小规模的二分图最大权匹配问题。常见应用场景包括：

• 任务分配（最大化总效益）
• 资源调度
• 多目标跟踪中的数据关联

总结

通过本教程，你已经掌握了KM算法的基本原理和C++实现方法。记住，KM算法是解决二分图最大权完美匹配的利器，而它本质上是对匈牙利算法的优化，专门处理带权情况。

建议你动手运行上述代码，修改输入数据，观察输出结果，加深理解。编程之路，实践出真知！

SEO关键词回顾：KM算法、C++实现、二分图最大权匹配、匈牙利算法优化