問題
$N$ 頂点 $M$ 辺の有向グラフ、容量付き。ソース $s=1$ とシンク $t=N$ の最小カット値（s-t を切断するために取り除く辺の容量の総和の最小値）を求めよ。
制約
$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: アプローチ
最大流を求めれば、その値が最小カット値と等しい。残余グラフで $s$ から到達可能な頂点集合 $S$ がカット側。
ヒント3: 誘導
最大流を流した後、残余グラフを $s$ から BFS で到達可能な頂点を求める。
模範解答 (Python)
import sys
from collections import deque
sys.setrecursionlimit(10000)
def main():
data = sys.stdin.read().split()
idx = 0
N, M = int(data[idx]), int(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(data[idx])-1, int(data[idx+1])-1, int(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
max_flow = 0
INF = float('inf')
while True:
visited = [False] * N
f = dfs(0, N-1, INF, visited)
if f == 0:
break
max_flow += f
print(max_flow)
reachable = [False] * N
queue = deque([0])
reachable[0] = True
while queue:
v = queue.popleft()
for e in graph[v]:
if not reachable[e[0]] and e[1] > 0:
reachable[e[0]] = True
queue.append(e[0])
main()Step-by-Step 解説
1最大流・最小カット定理
任意の s-t フロー最大化問題において「最大流量 = 最小カット容量」が成立。
任意の s-t フロー最大化問題において「最大流量 = 最小カット容量」が成立。
2最小カット辺の特定
最大流を流した残余グラフで $s$ から到達可能な頂点集合 $S$ → $S \to T$ への辺がカット辺。
最大流を流した残余グラフで $s$ から到達可能な頂点集合 $S$ → $S \to T$ への辺がカット辺。
3実用例
プロジェクト選択問題、画像セグメンテーション、ネットワーク信頼性解析など。
プロジェクト選択問題、画像セグメンテーション、ネットワーク信頼性解析など。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| カット辺を残余容量 0 の辺と混同 | 残余グラフと元グラフの混同 | 元グラフ容量>0 かつ残余容量0 の辺がカット辺 |
| 最大流と最小カットの関係を忘れる | 定理を知らない | 最大流 = 最小カットを暗記 |
| 非連結グラフを考慮しない | $s$ から $t$ に到達不能 | 最大流 0 なら既にカット済み |
次のステップ
- 発展問題: 無向グラフの最小カット（Global Min-Cut）を Stoer-Wagner アルゴリズムで