問題
$N \times N$ のコスト行列 $C$ で完全マッチングの総コストを最小化せよ。
制約
$1 \le N \le 500$
$0 \le C[i][j] \le 10^9$
入出力例
入力例 1
3
9 2 7
3 6 3
1 8 2出力例 1
70→1(2), 1→0(3), 2→2(2) → 合計 7
ヒント (段階的開示)
ヒント1: 方向性
Kuhn-Munkres の $O(N^3)$。ポテンシャル $(u[i], v[j])$ を更新。
ヒント2: アプローチ
縮小コスト $C[i][j] - u[i] - v[j] \ge 0$ を維持しつつ最適割り当てを探索。増加路なしならスラック最小辺で双対変数を更新。
ヒント3: Jonker-Volgenant
作業者を1人ずつ追加。
minVal[j] と way[j] で増加路を管理。模範解答 (Python)
import sys
input = sys.stdin.readline
def hungarian(C):
n = len(C)
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
minVal = [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 < minVal[j]:
minVal[j] = cur
way[j] = j0
if minVal[j] < delta:
delta = minVal[j]
j1 = j
for j in range(n + 1):
if used[j]:
u[p[j]] += delta
v[j] -= delta
else:
minVal[j] -= delta
j0 = j1
if p[j0] == 0:
break
while j0:
p[j0] = p[way[j0]]
j0 = way[j0]
total = 0
for j in range(1, n + 1):
if p[j] != 0:
total += C[p[j] - 1][j - 1]
return total
def main():
N = int(input())
C = []
for _ in range(N):
C.append(list(map(int, input().split())))
print(hungarian(C))
main()Step-by-Step 解説
1双対問題
$u[i], v[j]$ ポテンシャル。縮小コスト $\ge 0$ を維持。
$u[i], v[j]$ ポテンシャル。縮小コスト $\ge 0$ を維持。
2作業者を順に割り当て
BFS 的に増加路を探索、
BFS 的に増加路を探索、
minVal[j] 更新。3双対変数更新
未使用タスクへの最小縮小コスト delta で全 used 側を調整。
未使用タスクへの最小縮小コスト delta で全 used 側を調整。
4増加路復元
way 配列を逆順に辿る。5最終コスト
割り当てから直接 $C[p[j]-1][j-1]$ を合算。
割り当てから直接 $C[p[j]-1][j-1]$ を合算。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 1/0-indexed 混同 | 実装依存 | C[i0-1][j-1] |
| delta = INF のまま進む | 境界処理 | 大きな定数で初期化 |
| used 内外で更新を逆に | 条件ミス | used で u 加算・v 減算 |
| way の方向 | 逆順処理 | while j0: p[j0] = p[way[j0]]; j0 = way[j0] |
次のステップ
- $N \ne M$ の場合の最小重み最大マッチング
- 最大重みは符号反転で適用