KM算法

What · 是什么

KM 算法（Kuhn–Munkres 算法，又称匈牙利算法的带权版）求二分图的最大权完美匹配，O(n³)。它维护一组可行顶标 lx/ly（满足对任意边 w(u,v) ≤ lx(u)+ly(v)），定义相等子图为满足 w = lx+ly 的边构成的子图；不断调整顶标、在相等子图中找完美匹配，当相等子图出现完美匹配时，它就是最大权完美匹配（因任何完美匹配权值和 ≤ Σlx+Σly，相等子图匹配权值和 = Σlx+Σly）。对于非平衡/非完全二分图，通过补点（少的一侧补到相等）+ 缺失边权设 0 或 -inf 转为方阵问题。是解决指派问题（assignment problem）的经典 O(n³) 算法。

Why · 为什么

How · 实现

伪代码

# 平衡方阵 n×n，求最大权完美匹配 (缺失边设 -inf 或 0)
init: lx[i]=max_j w[i][j]; ly[j]=0
for i in 左部点:
  while True:
    visited_左/右 = False
    if dfs(i) 找到增广路: break
    a = min{ lx[u]+ly[v]-w[u][v] | u∈S(vis左), v∉T(vis右) }
    for u∈S: lx[u]-=a
    for v∉T: ly[v]+=a   # 等价于调整使新边进入相等子图
# O(n^3) 实现用 slack 数组 + BFS

Python 实现

def km_max_weight(weights):
    """Kuhn-Munkres 求最大权完美匹配 (O(n^3))。
    weights: n×n 二维数组，缺失边权值用 -INF。
    返回 (最大权和, match_row): match_row[i] = 第 i 行匹配的列。"""
    n = len(weights)
    INF = 10 ** 18
    # 最大权 → 对权值取负转最小指派（加常数不影响 argmin，故直接取负）
    a = [[-weights[i][j] for j in range(n)] for i in range(n)]
    u = [0] * (n + 1)      # 行顶标
    v = [0] * (n + 1)      # 列顶标
    p = [0] * (n + 1)      # 列匹配的行
    way = [0] * (n + 1)
    for i in range(1, n + 1):
        p[0] = i
        j0 = 0
        minv = [INF] * (n + 1)
        used = [False] * (n + 1)
        while True:
            used[j0] = True
            i0 = p[j0]
            delta = INF
            j1 = 0
            for j in range(1, n + 1):
                if not used[j]:
                    cur = a[i0 - 1][j - 1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j] = cur
                        way[j] = j0
                    if minv[j] < delta:
                        delta = minv[j]
                        j1 = j
            for j in range(n + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        while True:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
            if j0 == 0:
                break
    match_row = [0] * (n + 1)
    for j in range(1, n + 1):
        match_row[p[j]] = j
    total = sum(weights[i - 1][match_row[i] - 1] for i in range(1, n + 1))
    return total, [match_row[i] - 1 for i in range(1, n + 1)]


if __name__ == '__main__':
    import itertools, random

    def brute(a):
        best = -10 ** 18
        for perm in itertools.permutations(range(len(a))):
            s = sum(a[i][perm[i]] for i in range(len(a)))
            best = max(best, s)
        return best

    # 手测
    assert km_max_weight([[3, 1], [2, 1]])[0] == 4   # 选 3+1
    assert km_max_weight([[5, 4], [3, 6]])[0] == 11  # 选 5+6
    # 随机交叉验证（含负权）
    random.seed(5)
    for _ in range(500):
        n = random.randint(1, 5)
        a = [[random.randint(-10, 10) for _ in range(n)] for _ in range(n)]
        r1, _ = km_max_weight(a)
        r2 = brute(a)
        assert r1 == r2, (a, r1, r2)
    print('km-algorithm: All tests passed.')

易错点

• 朴素的 DFS 顶标调整（每次扫 S×T' 求 a）是 O(n⁴)，必须用 slack 数组维护到 O(n³)
• 最大权完美匹配要求方阵：矩形须补点并把缺失边设 -INF（不能设 0，会退化）
• 负权与 -INF 并存时初始化 lx=max 会把 -INF 也纳入，需逐行跳过 -INF
• 顶标更新顺序：S 中左点减 a、T 中右点加 a，写反导致相等子图变化方向错误
• way/p 数组重置：每轮 i 循环必须重置 used/minv，way 与 p 不清除会串
• 与匈牙利算法（无权增广路）同名易混：KM 是带权完美匹配 O(n³)，hungarian 是无权最大匹配 O(VE)

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/graph-matching/bigraph-weight-match/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/graph/graph-matching/bigraph-weight-match.md
• CP-Algorithms✓ https://cp-algorithms.com/graph/hungarian-algorithm.html
• 书籍✓ CPH ch20 pp191-204 (assignment problem)