問題
$N$ 頂点 $M$ 辺の有向グラフが与えられる（多重辺を許す。自己ループはない）。
頂点 $s$ から頂点 $t$ へ至る経路のうち、互いに辺を共有しない経路（辺素パス）を同時に最大何本取れるかを求めよ。
Menger の定理より、この値は「$s$ から $t$ への到達を断つために取り除く必要がある辺の最小本数（最小辺カット）」に一致する。したがって、各辺の容量を $1$ とした最大流問題として解けばよい。
入力形式
N M
u_1 v_1
:
u_M v_M
s t制約
$2 \le N \le 1000$
$1 \le M \le 2000$
$u_i \ne v_i$（多重辺あり）
$s \ne t$
入出力例
入力例1
4 5
1 2
1 3
2 4
3 4
1 4
1 4出力例1
31→4直接／1→2→4／1→3→4 の3本が互いに辺を共有せず、これが最大本数（=最小辺カット）。
概念図：3本の辺素パス
ヒント（段階的開示）
ヒント1（方向性）
経路をひとつずつ貪欲に探して重複辺を除いていく組合せ的アプローチは、探索順序によって最適本数を逃すことがある。「流れ」の概念、すなわちネットワークフローとして定式化すると、貪欲の失敗を避けて厳密な最適値を求められる。
ヒント2（アプローチ）
各辺の容量を$1$とみなし、$s$を始点、$t$を終点とする最大流問題を解く。最大流の値がそのまま辺素パスの最大本数になる（単位容量ネットワークの最適フローは必ず整数値になり、フロー分解定理によりパス上のフローに分解できる）。Menger の定理はこの最大流問題における max-flow min-cut 定理そのものである。
ヒント3（誘導）
from collections import deque
class MaxFlow:
def __init__(self, n):
self.n = n
self.graph = [[] for _ in range(n)]
self.to = []
self.cap = []
def add_edge(self, u, v, c):
self.graph[u].append(len(self.to)); self.to.append(v); self.cap.append(c)
self.graph[v].append(len(self.to)); self.to.append(u); self.cap.append(0)
def bfs_level(self, s):
level = [-1] * self.n
level[s] = 0
q = deque([s])
while q:
u = q.popleft()
for eid in self.graph[u]:
v = self.to[eid]
if self.cap[eid] > 0 and level[v] < 0:
level[v] = level[u] + 1
q.append(v)
return level
# dfs_flow は Dinic 法のブロッキングフロー探索（本文参照）模範解答 (Python)
import sys
from collections import deque
def main():
data = sys.stdin.buffer.read().split()
idx = 0
N = int(data[idx]); idx += 1
M = int(data[idx]); idx += 1
graph = [[] for _ in range(N + 1)]
to = []
cap = []
def add_edge(u, v, c):
graph[u].append(len(to)); to.append(v); cap.append(c)
graph[v].append(len(to)); to.append(u); cap.append(0)
for _ in range(M):
u = int(data[idx]); idx += 1
v = int(data[idx]); idx += 1
add_edge(u, v, 1)
s = int(data[idx]); idx += 1
t = int(data[idx]); idx += 1
def bfs():
level = [-1] * (N + 1)
level[s] = 0
q = deque([s])
while q:
u = q.popleft()
for eid in graph[u]:
v = to[eid]
if cap[eid] > 0 and level[v] < 0:
level[v] = level[u] + 1
q.append(v)
return level
def dfs(u, f, level, it):
if u == t:
return f
while it[u] < len(graph[u]):
eid = graph[u][it[u]]
v = to[eid]
if cap[eid] > 0 and level[v] == level[u] + 1:
d = dfs(v, min(f, cap[eid]), level, it)
if d > 0:
cap[eid] -= d
cap[eid ^ 1] += d
return d
it[u] += 1
return 0
flow = 0
while True:
level = bfs()
if level[t] < 0:
break
it = [0] * (N + 1)
while True:
f = dfs(s, float('inf'), level, it)
if f == 0:
break
flow += f
print(flow)
main()Step-by-Step 解説
1辺素パスと最大流の対応
各辺容量1の最大整数フロー値は、各辺を高々1回しか使わないs-tパスの最大同時本数に一致する（フロー分解定理）。
各辺容量1の最大整数フロー値は、各辺を高々1回しか使わないs-tパスの最大同時本数に一致する（フロー分解定理）。
2Mengerの定理
「s-t辺素パスの最大本数」=「s-t最小辺カットのサイズ」。max-flow min-cut定理の言い換えであり、Mengerが1927年にグラフ理論的に証明した結果。
「s-t辺素パスの最大本数」=「s-t最小辺カットのサイズ」。max-flow min-cut定理の言い換えであり、Mengerが1927年にグラフ理論的に証明した結果。
3Dinic法によるアルゴリズム
BFSでレベルグラフを構築し、DFSでブロッキングフローを求める。単位容量グラフではフェーズ数がO(√M)に抑えられる。
BFSでレベルグラフを構築し、DFSでブロッキングフローを求める。単位容量グラフではフェーズ数がO(√M)に抑えられる。
4経路の復元（発展）
残余グラフ上で容量が減った辺（フローが流れた辺）を辿ればs-tパスを1本ずつ復元できる。
残余グラフ上で容量が減った辺（フローが流れた辺）を辿ればs-tパスを1本ずつ復元できる。
5計算量
単位容量グラフでのDinic法はO(M√M)。M≤2000なので十分高速。
単位容量グラフでのDinic法はO(M√M)。M≤2000なので十分高速。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 逆辺の容量を無視し単純に「使った辺を消す」貪欲DFSで解こうとする | 最初に確保した経路が後の経路を阻害するケースを見逃す | 逆辺（容量0で初期化、流すたびに増える）を必ず持たせフローの取り消しを可能にする |
| 辺の容量を頂点数や重みと誤って設定する | 「重み」がない問題文で容量を何にすべきか迷う | 「辺素」条件そのものが各辺は最大1回しか使えないことを意味するため容量は必ず1 |
| 多重辺がある場合に片方を無視してしまう | 隣接リストを辞書やセットで管理し重複を除去してしまう | 多重辺はそれぞれ独立した容量1の辺として別々に追加する |
| BFSレベルが同じ深さの辺だけを辿らず全辺を辿ってしまう | レベルグラフの制約をDFSで確認し忘れる | Dinic法のDFSでは必ずレベルが1つ増える辺のみを辿るようチェックする |
| 現在辺ポインタを使い回さず毎回0から探索し計算量が悪化する | ブロッキングフロー中に同じ辺を何度も無駄に調べてしまう | 各頂点ごとに現在辺ポインタを保持し、探索済みの辺は二度と調べない |
次のステップ
- 発展: 「頂点素パス（vertex-disjoint paths）」に変えるとどうなるか考えよ（頂点分割トリック：各頂点を「入」「出」に分け容量1の辺で結ぶ）。
- 発展2: 重み付き辺（容量が任意）の最大流と、Mengerの定理の「頂点連結度」バージョン（Whitneyの定理）との関係を調べよ。