Day 050-Q3 | Hungarian Algorithm + Potential法（最大重みマッチング）

問題

$N \times N$ のコスト行列 $C[i][j]$ が与えられる。左側 $N$ 頂点 $u_1,\ldots,u_N$ と右側 $N$ 頂点 $v_1,\ldots,v_N$ の間の完全二部グラフで、辺 $(u_i, v_j)$ の重みを $C[i][j]$ とする。

完全マッチング（全頂点を使う）のうち、辺の重みの総和が最大のものを求めよ。

制約

$1 \le N \le 500$

$0 \le C[i][j] \le 10^9$

時間制限: 3秒

入出力例

入力例 1

出力例 1

入力例 2

出力例 2

例1: マッチング $(u_1,v_3)+(u_2,v_1)+(u_3,v_2)$ → $3+4+8=15$。例2: $(u_1,v_1)+(u_2,v_2)+(u_3,v_3)$ → $10+6+9=25$。

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

ヒント（段階的開示）

ヒント1: 方向性

最大重みマッチング → コスト反転（$\max(C) - C[i][j]$）して最小コストマッチングに帰着し、ハンガリアン法を適用する。

ヒント2: アプローチ

Potential 法（Johnson's Potential）を用いた $O(N^3)$ ハンガリアン法:

ポテンシャル $u[i], v[j]$ を初期化
縮小コスト $cost[i][j] - u[i] - v[j] \ge 0$ を常に保つ
各左頂点に対して Dijkstra 的な最短路で増加路を探索
増加路発見時に $\delta$ だけポテンシャルを調整

ヒント3: 実装の骨格

def hungarian_min(cost, N):
    INF = float('inf')
    u = [0]*(N+1); v = [0]*(N+1)
    p = [0]*(N+1)  # p[j] = jにマッチした左頂点
    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 = cost[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]
    return -v[0]

模範解答 (Python)

import sys
input = sys.stdin.readline

def hungarian_min(cost, N):
    """O(N^3) Hungarian Algorithm - 最小コスト完全マッチング"""
    INF = float('inf')
    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 = -1
            for j in range(1, N+1):
                if not used[j]:
                    cur = cost[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+1)
    for j in range(1, N+1):
        if p[j]: match[p[j]] = j
    total = sum(cost[i-1][match[i]-1] for i in range(1, N+1))
    return total, match

def solve():
    N = int(input())
    C = [list(map(int, input().split())) for _ in range(N)]
    max_val = max(max(row) for row in C)
    cost_inv = [[max_val - C[i][j] for j in range(N)] for i in range(N)]
    min_cost, match = hungarian_min(cost_inv, N)
    max_weight = max_val*N - min_cost
    print(max_weight)

solve()

Step-by-Step 解説

1問題の変換
最大重みマッチング → 最小コストマッチング（コスト $= \max(C) - C[i][j]$）。最終答え = $N \cdot \max(C) - \text{最小コスト}$。

2ポテンシャルの役割
ポテンシャル $u[i], v[j]$（双対変数）は縮小コスト $cost[i][j] - u[i] - v[j] \ge 0$ を常に保つ。この性質で擬似的に Bellman-Ford なしに Dijkstra が使える。

3左頂点を1つずつ追加
$i = 1, 2, \ldots, N$ と順番に処理。各ステップで仮想頂点 $p[0] = i$ から始め、Dijkstra 的に増加路を探索しマッチングを1辺増やす。

4way 配列による増加路追跡
$way[j]$ = 「右頂点 $j$ に来た直前の右頂点」。$p[j_0]=0$ になった時点で $way$ を遡りマッチングを更新。

5計算量
外ループ $N$ 回 × 内ループ最悪 $N$ 回 × 辺スキャン $N$ = $O(N^3)$。$N=500$ で約 1.25 億演算。Python では PyPy 推奨。

計算量

時間: $O(N^3)$
空間: $O(N^2)$（コスト行列）
$N=500$ での演算数: 約 $1.25 \times 10^8$

よくあるミス

ミス	原因	正しい書き方
コスト反転時に INF を使う	`max_val - INF` が負になる	`max_val = max(すべてのC[i][j])` で定義
1-indexed と 0-indexed の混在	添字ずれ	ポテンシャルは 1-indexed、cost は 0-indexed で統一
ポテンシャル更新で used[0] を忘れる	仮想頂点 0 の更新漏れ	ループを `range(N+1)` にする
最大重みの計算ミス	`max_val * N - min_cost` の `*N` を忘れる	反転前の総コスト = $N \cdot \max\_val$ - 最小コスト

次のステップ

発展問題: 一般グラフの最大重みマッチング（Blossom Algorithm 重み付き版）
関連: 最小費用流による Assignment Problem の別解（理解の比較）
応用: 列挙型 Assignment（上位 K 個のマッチングを求める問題）

自己評価

完全理解おおむね理解要復習