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

KM算法核心思想

KM算法通过维护两个顶标（label）数组 lx[] 和 ly[]，使得对于任意边 (i, j)，都有 lx[i] + ly[j] >= weight[i][j]。算法不断调整顶标，直到找到一个完美匹配，且所有匹配边都满足 lx[i] + ly[j] == weight[i][j]，此时总权值最大。

C语言实现步骤详解

下面我们将逐步实现KM算法。假设我们有一个 n×n 的权值矩阵 w[][]，表示二分图左右两边各 n 个节点之间的权重。

1. 初始化变量

#include <stdio.h>#include <string.h>#include <limits.h>#define MAXN 105  // 最大节点数#define INF INT_MAXint n;                    // 节点数量int w[MAXN][MAXN];        // 权值矩阵int lx[MAXN], ly[MAXN];   // 左右顶标int match[MAXN];          // 右侧节点匹配的左侧节点bool vx[MAXN], vy[MAXN];  // 访问标记int slack[MAXN];          // slack数组用于优化

2. 寻找增广路径的DFS函数

bool dfs(int u) {    vx[u] = true;    for (int v = 0; v < n; v++) {        if (vy[v]) continue;        int t = lx[u] + ly[v] - w[u][v];        if (t == 0) {            vy[v] = true;            if (match[v] == -1 || dfs(match[v])) {                match[v] = u;                return true;            }        } else if (slack[v] > t) {            slack[v] = t;        }    }    return false;}

3. KM算法主函数

int KM() {    // 初始化顶标    memset(ly, 0, sizeof(ly));    for (int i = 0; i < n; i++) {        lx[i] = -INF;        for (int j = 0; j < n; j++) {            if (w[i][j] > lx[i])                lx[i] = w[i][j];        }    }    // 初始化匹配    memset(match, -1, sizeof(match));    for (int i = 0; i < n; i++) {        while (true) {            memset(vx, false, sizeof(vx));            memset(vy, false, sizeof(vy));            for (int j = 0; j < n; j++)                slack[j] = INF;            if (dfs(i)) break;            // 更新顶标            int d = INF;            for (int j = 0; j < n; j++)                if (!vy[j] && slack[j] < d)                    d = slack[j];            for (int j = 0; j < n; j++) {                if (vx[j]) lx[j] -= d;                if (vy[j]) ly[j] += d;                else slack[j] -= d;            }        }    }    // 计算最大权值和    int result = 0;    for (int i = 0; i < n; i++)        result += w[match[i]][i];    return result;}

4. 主函数测试

int main() {    // 示例：3x3 权值矩阵    n = 3;    int weights[3][3] = {        {3, 2, 4},        {1, 5, 2},        {2, 1, 3}    };    for (int i = 0; i < n; i++)        for (int j = 0; j < n; j++)            w[i][j] = weights[i][j];    int maxWeight = KM();    printf("最大权匹配值为: %d\n", maxWeight);    // 输出匹配结果    for (int j = 0; j < n; j++)        printf("左节点 %d 匹配右节点 %d\n", match[j], j);    return 0;}

常见问题与优化

- 时间复杂度：朴素KM算法为 O(n⁴)，但通过使用 slack 数组可优化至 O(n³)。
- 适用范围：仅适用于完全二分图（即左右节点数相等且存在完美匹配）。
- 负权处理：若存在负权，需先对权值整体偏移使其非负。

总结

通过本教程，你应该已经掌握了KM算法的基本原理和C语言实现方法。无论是解决实际分配问题，还是应对算法竞赛，这套代码都能为你提供坚实基础。记住，理解二分图最大权匹配的核心在于顶标的维护与调整，而匈牙利算法优化的思想贯穿始终。

提示：建议将上述代码保存为 km_algorithm.c 并使用 GCC 编译运行，观察输出结果加深理解。