Kuhn-Munkres带权二分图最大权匹配

作者： /

问题定义

KM 算法（Kuhn-Munkres）解决带权二分图的最大权完备匹配：给定二分图（顶点分 X、Y 两组），每条边有权值，求权值和最大的匹配。它通过”顶标”把最大权匹配问题转化为相等子图上的完备匹配问题，配合匈牙利算法找增广路，复杂度可优化到 O(n³)。

核心思想

1. 顶标（Vertex Label）

给每个顶点一个数值：X 顶点顶标 lx[i]，Y 顶点顶标 ly[j]，约束：

lx[i] + ly[j] ≥ w(i, j)

即任意边的权值不超过两端顶标之和。

2. 相等子图与关键定理

由满足 lx[i] + ly[j] = w(i, j) 的边构成的子图称为相等子图。关键定理：若相等子图存在完备匹配，则该匹配就是原图的最大权匹配。证明思路：任意匹配的边权和 ≤ 任意时刻所有顶标和（因为每条匹配边都 ≤ 两端顶标和），而相等子图的完备匹配恰好达到这个上界。

因此算法变成：不断调整顶标、扩大相等子图，直到找到完备匹配。

算法流程

  1. 初始化顶标：lx[i] = max(w(i,j))（该行最大边权），ly[j] = 0；
  2. 找增广路：对每个 X 顶点，在相等子图上用匈牙利算法的 DFS/BFS 找增广路，找到则反转路径、扩大匹配；
  3. 顶标调整：找不到增广路时，计算松弛量 delta = min(lx[i] + ly[j] - w(i,j))（i 在交错树中、j 不在），把交错树中的 X 顶标减 delta、Y 顶标加 delta——这样原相等子图的边保持不变，且至少引入一条新边，相等子图逐步扩大；
  4. 重复 2–3，直到所有 X 顶点都匹配上。

复杂度与优化

  • 朴素实现：每次调整都全量扫描算 delta，O(n⁴)；
  • 松弛表优化（slack[j]）：维护每个 Y 顶点的最小松弛量，调整顶标时只更新 slack，增广路搜索不再全量重算，降到 O(n³)，可支撑 n ≤ 500 左右的规模；
  • 用 BFS 代替 DFS 实现匈牙利部分，避免递归过深，也是常见的常数优化。

C++ 实现（BFS + slack 优化）


#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

const int MAXN = 305;

class KuhnMunkres {
private:
    int n;
    int w[MAXN][MAXN];
    int lx[MAXN], ly[MAXN];
    bool visy[MAXN];
    int slack[MAXN];
    int match[MAXN];   // match[y] = 匹配到哪个 X
    int prev[MAXN];    // BFS 路径

    void bfs(int start) {
        memset(prev, 0, sizeof(prev));
        memset(slack, 0x3f, sizeof(slack));
        int y = 0, next_y = 0;
        match[y] = start;              // 哨兵：0 号 Y 先虚拟匹配 start
        do {
            int x = match[y], delta = INT_MAX;
            visy[y] = true;
            for (int j = 1; j <= n; j++) {
                if (visy[j]) continue;
                int gap = lx[x] + ly[j] - w[x][j];
                if (slack[j] > gap) { slack[j] = gap; prev[j] = y; }
                if (slack[j] < delta) { delta = slack[j]; next_y = j; }
            }
            for (int j = 0; j <= n; j++) {   // 调整顶标
                if (visy[j]) { lx[match[j]] -= delta; ly[j] += delta; }
                else slack[j] -= delta;
            }
            y = next_y;
        } while (match[y] != 0);

        while (y != 0) {                // 沿 prev 反转增广路
            match[y] = match[prev[y]];
            y = prev[y];
        }
    }

public:
    void init(int size) { n = size; memset(w, 0, sizeof(w)); }
    void addEdge(int u, int v, int weight) { w[u][v] = weight; }

    int solve() {
        memset(lx, 0, sizeof(lx));
        memset(ly, 0, sizeof(ly));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                lx[i] = max(lx[i], w[i][j]);
        memset(match, 0, sizeof(match));

        for (int i = 1; i <= n; i++) {
            memset(visy, 0, sizeof(visy));
            bfs(i);
        }
        int sum = 0;
        for (int j = 1; j <= n; j++)
            if (match[j]) sum += w[match[j]][j];
        return sum;
    }
};

int main() {
    KuhnMunkres km;
    int n = 3;
    km.init(n);
    // 3x3 权重矩阵：
    //   2 3 3
    //   3 2 3
    //   3 3 2
    km.addEdge(1, 1, 2); km.addEdge(1, 2, 3); km.addEdge(1, 3, 3);
    km.addEdge(2, 1, 3); km.addEdge(2, 2, 2); km.addEdge(2, 3, 3);
    km.addEdge(3, 1, 3); km.addEdge(3, 2, 3); km.addEdge(3, 3, 2);

    cout << "最大权匹配值: " << km.solve() << endl; // 9
    return 0;
}

测试用例说明

对上面的 3×3 矩阵，最优匹配为 (1,3)、(2,1)、(3,2)，权值和 = 3+3+3 = 9（不存在更大的完备匹配）。

注意事项

  • KM 默认求完备匹配；图不满足完备性时，用权值 0 的边补成完全图即可；
  • 若要求最小权匹配，把边权取负后用 KM 求最大即可；
  • 存在负权边时，顶标初始化要相应调整（lx 初始化为行最大，可能为负，需要特殊处理）；
  • 若只需”最大权但不要求完备”，补零边 + 输出时跳过 0 边通常即可。

应用场景

任务分配（n 个任务给 n 个工人最大化总效率）、资源调度、传感器/特征点匹配、DNA 序列最优比对等所有”双边一一分配取最大收益”的问题。

相关文章

滚动至顶部