Day 059-Q3 — 最小コスト完全マッチング（Hungarian Algorithm）

問題

$N \times N$ のコスト行列 $C$ が与えられる。$C[i][j]$ は左側頂点 $i$ を右側頂点 $j$ に割り当てるコスト。全左側頂点と全右側頂点の完全マッチングのうち、総コスト最小のものを求めよ。最小コストを出力し、次の行にマッチング $p[0..N-1]$（$p[i]$ = 頂点 $i$ に対応する右側頂点、0-indexed）を出力せよ。

入出力例

3
9 2 7
3 6 3
7 3 1

6
1 2 2

左0→右1(コスト2), 左1→右0(コスト3), 左2→右2(コスト1) → 合計6。
※ $p[1]=0, p[2]=2$ 等は一例（同コストのマッチが複数ある場合は任意の一つ）。

概念図: Hungarian Algorithm のポテンシャル

ヒント（段階的開示）

# p[j] = i: 右j に割り当てられた左i (1-indexed, p[0]=i は仮想)
# way[j]: Dijkstra の predecessor
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 = -1
        for j in range(1, N+1):
            if not used[j]:
                cur = C[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 j0: p[j0] = p[way[j0]]; j0 = way[j0]

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

def main():
    N = int(input())
    C = [list(map(int, input().split())) for _ in range(N)]

    INF = float('inf')
    u = [0]*(N+1); v = [0]*(N+1)
    p = [0]*(N+1)  # p[j] = i: 右j に左i が割り当て
    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 = -1
            for j in range(1, N+1):
                if not used[j]:
                    cur = C[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 j0:
            p[j0] = p[way[j0]]
            j0 = way[j0]

    match = [0]*N
    for j in range(1, N+1):
        if p[j]:
            match[p[j]-1] = j-1

    ans = sum(C[i][match[i]] for i in range(N))
    print(ans)
    print(*match)

main()

Step-by-Step 解説

Step 1: ポテンシャルの概念

双対変数 $u[i]$, $v[j]$ を管理。reduced cost $= C[i][j] - u[i] - v[j] \ge 0$ を常に保つ。マッチング辺は等号（tight）。

Step 2: 仮想頂点のトリック

p[0] = i として左頂点 $i$ を仮想右頂点 0 に割り当てたとみなして処理を開始。増加路が完成したら p[j0] == 0 となる。

Step 3: Dijkstra 的探索

minv[j] = 仮想起点から右頂点 $j$ への最小 reduced cost。delta = minv の最小値（未使用）を選び、ポテンシャルを更新して次の tight edge を追加。

Step 4: 増加路の適用

way 配列を辿って p（マッチング）を切り替え。$O(N)$。

Step 5: 計算量

外側ループ $N$ 回、各回 $O(N^2)$。合計 $O(N^3)$。$N=500$ で約 $1.25 \times 10^8$。

よくあるミス

次のステップ

発展問題: 辺に容量制限がある最小費用最大流（MCMF）と Hungarian の対応を理解し、$N=1000$ の問題に対して Python で最適化実装せよ。

自己評価