問題
$N$ 頂点 $M$ 辺の平面グラフで $s \to t$ 最大流を $O(M \log M)$ で求めよ。
制約
$2 \le N \le 10^5$
$N-1 \le M \le 10^6$
$1 \le c_i \le 10^9$
平面グラフ・$s=1, t=N$
入出力例
入力例 1
4 5
1 2 3
2 4 2
1 3 1
3 4 4
2 3 2
1 4出力例 1
4ヒント (段階的開示)
ヒント1: 方向性
平面グラフ $s$-$t$ 最大流 = 双対グラフの $s^*$-$t^*$ 最短路。
ヒント2: アプローチ
面を列挙 → 双対辺構築 → ダイクストラ。$O(M \log M)$ で通過。
ヒント3: 面の列挙
有向辺 $(u\to v)$ の次の面境界辺は $v$ の隣接リストで $u$ の直前（時計回り）の辺。
模範解答 (Python)
import sys
from heapq import heappush, heappop
from collections import defaultdict
from sys import stdin
def solve():
data = stdin.buffer.read().split()
idx = 0
N, M = int(data[idx]), int(data[idx+1]); idx += 2
edges = []
for i in range(M):
u, v, c = int(data[idx])-1, int(data[idx+1])-1, int(data[idx+2])
idx += 3
edges.append((u, v, c))
s, t = int(data[idx])-1, int(data[idx+1])-1; idx += 2
adj = defaultdict(list)
for i, (u, v, c) in enumerate(edges):
adj[u].append((v, i, c))
adj[v].append((u, i, c))
pos_in_adj = defaultdict(dict)
for v in adj:
for i, (u, _, _) in enumerate(adj[v]):
pos_in_adj[v][u] = i
def next_ccw(u, v):
nbrs = adj[v]
i = pos_in_adj[v][u]
j = (i - 1) % len(nbrs)
return nbrs[j][0]
face_of_dart = {}
face_id = 0
for u in range(N):
for v, ei, _ in adj[u]:
if (u, v) not in face_of_dart:
a, b = u, v
while (a, b) not in face_of_dart:
face_of_dart[(a, b)] = face_id
c = next_ccw(a, b)
a, b = b, c
face_id += 1
F = face_id
dual_adj = defaultdict(list)
for i, (u, v, c) in enumerate(edges):
f1 = face_of_dart.get((u, v), -1)
f2 = face_of_dart.get((v, u), -1)
if f1 != -1 and f2 != -1 and f1 != f2:
dual_adj[f1].append((f2, c))
dual_adj[f2].append((f1, c))
src_dual = 0
dst_dual = 1
INF = float('inf')
dist = [INF] * F
dist[src_dual] = 0
pq = [(0, src_dual)]
while pq:
d, v = heappop(pq)
if d > dist[v]:
continue
for w, c in dual_adj[v]:
if dist[v] + c < dist[w]:
dist[w] = dist[v] + c
heappush(pq, (dist[w], w))
print(dist[dst_dual] if dist[dst_dual] < INF else -1)
solve()Step-by-Step 解説
1双対グラフ
各面 → 双対頂点、各辺 → 双対辺（容量を重みに）。Euler: $F = E - V + 2$。
各面 → 双対頂点、各辺 → 双対辺（容量を重みに）。Euler: $F = E - V + 2$。
2最大流 = 最短路
定理: 平面グラフで $s$-$t$ 最大流 = $s^*$-$t^*$ 最短路。
定理: 平面グラフで $s$-$t$ 最大流 = $s^*$-$t^*$ 最短路。
3面の列挙
次の面境界辺 = 隣接リストの直前辺。$O(E)$。
次の面境界辺 = 隣接リストの直前辺。$O(E)$。
4計算量比較
Dinic $O(V^2 E)$ vs 双対 $O(E \log E)$。$M = 10^6$ では双対が必須。
Dinic $O(V^2 E)$ vs 双対 $O(E \log E)$。$M = 10^6$ では双対が必須。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 面の同定ミス | $s^*, t^*$ を間違える | $s$ 隣接面 vs $t$ 隣接面を特定 |
| 双対辺の重み | 容量と混同 | 重みは元の容量 |
| 多重辺の処理 | 同面間に複数辺 | 最短路で最小を選ぶ |
次のステップ
- 双対最短路から最小カット辺集合の復元