問題
$N$人の作業者と$M$個の仕事がある（$N\le M$）。作業者$i$を仕事$j$に割り当てるコストは$C_{i,j}$。すべての作業者に、互いに異なる仕事をちょうど1つずつ割り当てるとき、コストの合計を最小化せよ。
仮想始点$S$、仮想終点$T$を用意し、$S\to$作業者(容量1,コスト0)、作業者$\to$仕事(容量1,コスト$C_{i,j}$)、仕事$\to T$(容量1,コスト0)という3層のグラフを考えると、これは最小費用最大流問題として定式化できる。Successive Shortest Path法で残余グラフ上の最短路を1本ずつ見つけて流すことを繰り返せば、最小費用最大流が得られる。
入力形式
N M
C_11 C_12 ... C_1M
...
C_N1 ... C_NM制約
$1 \le N \le M \le 300$
$1 \le C_{i,j} \le 10^9$
入出力例
入力例1
2 2
1 3
2 1出力例1
2作業者1→仕事1(コスト1)、作業者2→仕事2(コスト1)で合計2が最小。逆の割当だと$3+2=5$で損。
概念図: 二部グラフ上の最小費用流
ヒント（段階的開示）
ヒント1: 方向性
ハンガリアン法(Kuhn-Munkres法)で$O(N^3)$で解けることを知っているかもしれないが、同じ問題はグラフの「フロー」の枠組みでも自然に解ける。始点→作業者→仕事→終点、という3層のグラフを考えてみよう。
ヒント2: アプローチ
$S\to$作業者(容量1,コスト0)、作業者$\to$仕事(容量1,コスト$C_{i,j}$)、仕事$\to T$(容量1,コスト0)の辺を張る。$S$から$T$への流量$N$の最小費用フローが最小コスト割当に対応する。残余グラフ上で$S\to T$の最短路を見つけ流せるだけ流すことを、流量が$N$になるまで繰り返す。負辺（キャンセル辺）が現れるためDijkstra法ではなくSPFA（Bellman-Ford系）を使う。
ヒント3: 誘導（コード骨格）
from collections import deque
def spfa(graph, S, T, V):
INF = float('inf')
dist = [INF]*V; dist[S] = 0
in_queue = [False]*V; prev = [None]*V
dq = deque([S]); in_queue[S] = True
while dq:
u = dq.popleft(); in_queue[u] = False
for e in graph[u]:
v, cap, cost, rev = e
if cap > 0 and dist[u] + cost < dist[v]:
dist[v] = dist[u] + cost
prev[v] = (u, e)
if not in_queue[v]:
dq.append(v); in_queue[v] = True
return dist, prev
# S→TのSPFAをN回繰り返し、毎回の最短路に沿って流せるだけ流し
# (流量 × 最短路長) を答えに加算する模範解答 (Python)
import sys
from collections import deque
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
n = int(data[idx]); idx += 1
m = int(data[idx]); idx += 1
cost = []
for i in range(n):
row = list(map(int, data[idx:idx + m])); idx += m
cost.append(row)
v_count = n + m + 2
s = n + m
t = n + m + 1
graph = [[] for _ in range(v_count)]
def add_edge(u, v, cap, c):
graph[u].append([v, cap, c, len(graph[v])])
graph[v].append([u, 0, -c, len(graph[u]) - 1])
for i in range(n):
add_edge(s, i, 1, 0)
for j in range(m):
add_edge(n + j, t, 1, 0)
for i in range(n):
for j in range(m):
add_edge(i, n + j, 1, cost[i][j])
INF = float('inf')
total_cost = 0
flow = 0
while flow < n:
dist = [INF] * v_count
in_queue = [False] * v_count
prev = [None] * v_count
dist[s] = 0
dq = deque([s])
in_queue[s] = True
while dq:
u = dq.popleft()
in_queue[u] = False
for e in graph[u]:
to, cap, c, rev = e
if cap > 0 and dist[u] + c < dist[to]:
dist[to] = dist[u] + c
prev[to] = (u, e)
if not in_queue[to]:
dq.append(to)
in_queue[to] = True
if dist[t] == INF:
break
d = INF
v = t
while v != s:
u, e = prev[v]
d = min(d, e[1])
v = u
v = t
while v != s:
u, e = prev[v]
e[1] -= d
graph[v][e[3]][1] += d
v = u
flow += d
total_cost += d * dist[t]
print(total_cost)
solve()計算量: $O(F \cdot V \cdot E)$（$F=N$回の augmenting path、各回 SPFA は $O(V\cdot E)$）。サンプルで出力2を確認済み。
Step-by-Step 解説
1ネットワークの構築
$S\to$作業者、作業者$\to$仕事、仕事$\to T$の3層グラフを作る。$S\to T$の流量$N$のフローが割当と1対1対応する。
$S\to$作業者、作業者$\to$仕事、仕事$\to T$の3層グラフを作る。$S\to T$の流量$N$のフローが割当と1対1対応する。
2SPFAで最短路を求める
残余グラフの負辺（キャンセル辺）に対応するため、Dijkstra法ではなくSPFAで$S\to T$の最短路を求める。
残余グラフの負辺（キャンセル辺）に対応するため、Dijkstra法ではなくSPFAで$S\to T$の最短路を求める。
3増加分の計算と反映
最短路上の残余容量の最小値$d$だけ流し、辺の容量を更新する。コストは$d\times\text{(最短路長)}$を加算。
最短路上の残余容量の最小値$d$だけ流し、辺の容量を更新する。コストは$d\times\text{(最短路長)}$を加算。
4繰り返しと停止
流量が$N$に達するまで、または経路が見つからなくなるまで繰り返す。
流量が$N$に達するまで、または経路が見つからなくなるまで繰り返す。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 負辺があるのにDijkstra法を使う | Dijkstra法は負辺があると正しく動作しない | SPFA（またはポテンシャル法+Dijkstra）を使う |
| 逆辺のコストの符号を反転し忘れる | キャンセル操作ができず最適解を逃す | `add_edge`で逆辺コストを必ず`-c`にする |
| 流量`d`を常に1固定にする | 今回は全容量1で偶然動くが一般には誤り | 経路上の残余容量の最小値を都度計算する |
| コストを辺の単純合計で再計算する | そのステップの最短路長を使わず二重計算になる | `total_cost += d * dist[t]`を使う |
次のステップ
- 発展: ポテンシャル法(Johnson's algorithm)を導入しDijkstra法(ヒープ)でO(F・E log V)に高速化する
- 発展: ハンガリアン法(O(N^3))と計算量・実装の複雑さを比較する
- 次回予告: 次回セッションでも引き続きMaster Levelの多様なテーマを扱う