問題
$N$ 頂点 $M$ 辺の無向重み付きグラフが与えられる。大域最小カット（頂点集合を2つの非空部分 $S,V\setminus S$ に分割したときの、両者間を結ぶ辺重み総和の最小値）を求めよ。
以下の定理を利用する。
頂点 $0$ を固定する。$t=1,\dots,N-1$ について $\text{maxflow}(0,t)$ を計算すると、大域最小カット $=\min_t \text{maxflow}(0,t)$ が成り立つ。
直感: 大域最小カット $(S,V\setminus S)$ において頂点0はどちらか一方に属する。頂点0の反対側に $t$ を選べば $\text{maxflow}(0,t)\le$ 大域最小カット。逆に各 $\text{maxflow}(0,t)$ 自体が何らかの切断なので、大域最小カット $\le\min_t\text{maxflow}(0,t)$。両者を合わせて等号成立。
無向辺 $\{u,v\}$（重み $w$）は $u\to v$，$v\to u$ の2本の有向辺（各容量 $w$）として扱う。
入力形式
N M
u_1 v_1 w_1
:
u_M v_M w_M制約
入出力例
入力例1
4 5
0 1 2
0 2 3
1 2 2
1 3 3
2 3 4出力例1
5頂点0単独のカット（次数和 2+3=5）が最小。maxflow(0,1)=maxflow(0,2)=maxflow(0,3)=5となり最小値5が大域最小カットと一致する。
概念図：固定始点からのN-1回max-flow
ヒント（段階的開示）
ヒント1（方向性）
大域最小カットは全分割 $2^{N-1}-1$ 通りを試せば求まるが指数的。s-t最小カット（＝s-t最大流）は多項式時間で解けるので、これをうまく使い回して大域最小カットに帰着したい。
ヒント2（アプローチ）
任意の大域最小カット $(S,V\setminus S)$ で頂点0は必ずどちらかに属する。頂点0の反対側にある頂点 $t$ を選べば $\text{maxflow}(0,t)$ はこのカットを候補として含む。全ての $t\ne0$ を試せば必ず一度は大域最小カットの反対側の頂点を $t$ として捉えられる。
ヒント3（誘導）
def dinic_maxflow(N, capacity, s, t):
INF = float('inf')
total_flow = 0
while True:
level = [-1] * N
level[s] = 0
queue = [s]
for u in queue:
for v in range(N):
if capacity[u][v] > 0 and level[v] == -1:
level[v] = level[u] + 1
queue.append(v)
if level[t] == -1:
return total_flow
# DFSでブロッキングフロー（省略）
...各 $t$ ごとに容量行列を複製してから呼び出すこと。$N\le10$ならDinic法を9回呼んでも余裕で間に合う。
模範解答 (Python)
import sys
from copy import deepcopy
def dinic_maxflow(N, capacity, s, t):
INF = float('inf')
total_flow = 0
while True:
level = [-1] * N
level[s] = 0
queue = [s]
head = 0
while head < len(queue):
u = queue[head]; head += 1
for v in range(N):
if capacity[u][v] > 0 and level[v] == -1:
level[v] = level[u] + 1
queue.append(v)
if level[t] == -1:
return total_flow
it = [0] * N
def dfs(u, f):
if u == t:
return f
while it[u] < N:
v = it[u]
if capacity[u][v] > 0 and level[v] == level[u] + 1:
d = dfs(v, min(f, capacity[u][v]))
if d > 0:
capacity[u][v] -= d
capacity[v][u] += d
return d
it[u] += 1
return 0
while True:
f = dfs(s, INF)
if f == 0:
break
total_flow += f
return total_flow
def main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
M = int(data[idx]); idx += 1
base_capacity = [[0] * N for _ in range(N)]
for _ in range(M):
u = int(data[idx]); idx += 1
v = int(data[idx]); idx += 1
w = int(data[idx]); idx += 1
base_capacity[u][v] += w
base_capacity[v][u] += w
best = float('inf')
for t in range(1, N):
cap_copy = deepcopy(base_capacity)
f = dinic_maxflow(N, cap_copy, 0, t)
best = min(best, f)
print(best)
main()Step-by-Step 解説
無向辺$\{u,v\}$（重み$w$）を、$u\to v$と$v\to u$の両方向に容量$w$を加算する形で隣接行列に落とし込む。
頂点0を始点に固定し$t=1,\dots,N-1$についてDinic法で最大流を求める。各$t$ごとに容量行列をコピーし直すことが重要。
$N-1$個の$\text{maxflow}(0,t)$の最小値が大域最小カットの値と一致する。
本来のHao-Orlinは前回のpreflowを引き継ぎ活性頂点の選択規則を工夫することで全体O(NM log(N²/M))を達成する。Stoer-Wagner法（頂点縮約方式）とも異なる第三のアプローチ。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 容量行列を使い回して答えが小さくなりすぎる | 前回のDinic計算で容量を消費したまま次を計算 | `deepcopy`で毎回容量行列を複製する |
| 無向辺を片方向にしか容量を張らない | 有向グラフの感覚で実装 | $u\to v$と$v\to u$の両方に同じ重みの容量を加算 |
| $t=0$自身を含めてループしてしまう | ループ範囲を`range(N)`にする | `range(1, N)`で始点自身を除く |
| 多重辺で片方の辺の容量を上書きする | `capacity[u][v]=w`と代入 | `capacity[u][v]+=w`で加算 |
| Dinic法のlevel配列を使い回す | ループ外で1回だけ初期化 | 毎フェーズでlevel配列を作り直す |
次のステップ
- 発展: preflowを再利用するHao-Orlinの高速化版を実装し、Dinic法をゼロから呼ぶ版とaugment回数を比較せよ。
- 次回予告: Nemhauser-Trotter定理（頂点被覆問題のLP緩和・最大流帰着による半整数解の構成）