問題
$N$ 頂点 $M$ 辺の有向グラフがある。各辺には容量が設定されている。頂点 1（ソース）から頂点 $N$（シンク）へ流せる最大流量を求めよ。
制約
$2 \le N \le 500$
$1 \le M \le 1000$
$1 \le c_i \le 10^4$
入出力例
入力例 1
4 5
1 2 10
1 3 10
2 3 2
2 4 8
3 4 10出力例 1
18ヒント (段階的開示)
ヒント1: 方向性
ソースからシンクへ流せる経路を繰り返し見つけ、各経路で流せる量を加算。
ヒント2: アプローチ
「増加路」を DFS で見つけ、ボトルネック容量を流す。逆辺（残余グラフ）を管理して取り消しも可能。
ヒント3: 誘導
def add_edge(u, v, cap):
graph[u].append([v, cap, len(graph[v])])
graph[v].append([u, 0, len(graph[u])-1]) # 逆辺模範解答 (Python)
import sys
sys.setrecursionlimit(10000)
def main():
input_data = sys.stdin.read().split()
idx = 0
N, M = int(input_data[idx]), int(input_data[idx+1]); idx += 2
graph = [[] for _ in range(N)]
def add_edge(u, v, cap):
graph[u].append([v, cap, len(graph[v])])
graph[v].append([u, 0, len(graph[u])-1])
for _ in range(M):
u, v, c = int(input_data[idx])-1, int(input_data[idx+1])-1, int(input_data[idx+2])
idx += 3
add_edge(u, v, c)
def dfs(v, t, f, visited):
if v == t:
return f
visited[v] = True
for e in graph[v]:
if not visited[e[0]] and e[1] > 0:
d = dfs(e[0], t, min(f, e[1]), visited)
if d > 0:
e[1] -= d
graph[e[0]][e[2]][1] += d
return d
return 0
flow = 0
INF = float('inf')
while True:
visited = [False] * N
f = dfs(0, N-1, INF, visited)
if f == 0:
break
flow += f
print(flow)
main()Step-by-Step 解説
1残余グラフ
辺 $(u\to v, cap=c)$ を使って $f$ 流すと、残余辺 $(u\to v, cap=c-f)$ と逆辺 $(v\to u, cap=f)$ が生まれる。
辺 $(u\to v, cap=c)$ を使って $f$ 流すと、残余辺 $(u\to v, cap=c-f)$ と逆辺 $(v\to u, cap=f)$ が生まれる。
2増加路の探索
残余グラフ上で $s$ から $t$ へのパスを DFS で探す。
残余グラフ上で $s$ から $t$ へのパスを DFS で探す。
3収束の保証
各反復で少なくとも 1 流れるため、最大流量 $F$ 回で終了。計算量 $O(FE)$。
各反復で少なくとも 1 流れるため、最大流量 $F$ 回で終了。計算量 $O(FE)$。
4逆辺インデックス管理
add_edge 時に rev_index を保存し、後で
add_edge 時に rev_index を保存し、後で
graph[e[0]][e[2]][1] += d で逆辺を更新。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 逆辺を追加しない | 残余グラフの概念を知らない | add_edge(v, u, 0) |
| 逆辺の更新を間違える | インデックス管理ミス | add_edge 時に rev_index を保存 |
| 再帰上限エラー | 大きいグラフで DFS が深い | sys.setrecursionlimit(10**6) または BFS |
次のステップ
- 発展問題: Dinic 法で $O(V^2 E)$ の最大流