Day 098-Q4 | Capacity Scaling法（最大流のスケーリング高速化）

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺 $(u,v)$ には容量 $c$ が定められている。頂点 $S$ から頂点 $T$ への最大流量を求めよ。

単純なEdmonds-Karp法ではなく、Capacity Scaling法を用いて計算せよ。「容量が大きい辺から優先的に使う」ことで反復回数を大幅に削減する古典的な高速化手法である。

$\Delta$ を辺の最大容量以下の最大の2べきに初期化する。
残余容量が $\Delta$ 以上の辺のみを使ってBFSで増加路を探索し、見つかった限り流し続ける。
増加路が見つからなくなったら $\Delta \leftarrow \Delta/2$ とし、$\Delta \ge 1$ である限り2に戻る。
$\Delta < 1$ になったら終了し総流量を出力する。

入力形式

N M S T
u_1 v_1 c_1
:
u_M v_M c_M

制約

$2 \le N \le 500$

$1 \le M \le 5000$

$1 \le c_i \le 10^9$

多重辺・自己ループが存在する場合あり

入出力例

入力例1

出力例1

最小カットは頂点0からの出辺 (0→1:3) + (0→2:2) = 5。経路 0→1→3(2), 0→2→3(2), 0→1→2→3(1) で流量5を達成できる。

概念図

ヒント（段階的開示）

ヒント1: 方向性

Edmonds-Karp法は正しく最大流を求められるが、容量が大きい入力では反復回数が容量に依存して増えることがある。「一度に流す量」に下限を設けて、大きい流れから優先的に確定させていくとどうなるか考えよ。

ヒント2: アプローチ

スケーリングパラメータ $\Delta$ を導入し、「残余容量が $\Delta$ 以上の辺だけを使う」制約付きグラフでBFS増加路探索を繰り返す。$\Delta$ をだんだん半分にしていくことで各フェーズでの増加路の本数を $O(E)$ 程度に抑えられ、全体の計算量は $O(E^2\log U)$（$U$は最大容量）となる。最終的な流量は通常のFord-Fulkerson法と同じ真の最大流に一致する。

ヒント3: 誘導（コード骨格）

delta = 1
while delta * 2 <= max_cap:
    delta *= 2

max_flow = 0
while delta >= 1:
    while True:
        path = bfs_find_path(delta)  # 残余容量 >= delta の辺だけを使う
        if path is None:
            break
        bottleneck = min(residual capacities along path)
        # path に沿って bottleneck だけ流す
        max_flow += bottleneck
    delta //= 2

模範解答 (Python)

import sys
from collections import deque


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    s = int(data[idx]); idx += 1
    t = int(data[idx]); idx += 1

    graph = [[] for _ in range(n)]  # graph[u] = [to, cap, rev_index]
    max_cap = 1
    for _ in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        graph[u].append([v, c, len(graph[v])])
        graph[v].append([u, 0, len(graph[u]) - 1])
        max_cap = max(max_cap, c)

    delta = 1
    while delta * 2 <= max_cap:
        delta *= 2

    def bfs_find_path(delta):
        parent_edge = [None] * n
        visited = [False] * n
        visited[s] = True
        q = deque([s])
        while q:
            u = q.popleft()
            if u == t:
                break
            for ei, e in enumerate(graph[u]):
                to, cap, rev = e
                if not visited[to] and cap >= delta:
                    visited[to] = True
                    parent_edge[to] = (u, ei)
                    q.append(to)
        if not visited[t]:
            return None
        path = []
        v = t
        while v != s:
            u, ei = parent_edge[v]
            path.append((u, ei))
            v = u
        path.reverse()
        return path

    max_flow = 0
    while delta >= 1:
        while True:
            path = bfs_find_path(delta)
            if path is None:
                break
            bottleneck = min(graph[u][ei][1] for u, ei in path)
            for u, ei in path:
                e = graph[u][ei]
                to = e[0]
                rev = e[2]
                e[1] -= bottleneck
                graph[to][rev][1] += bottleneck
            max_flow += bottleneck
        delta //= 2

    print(max_flow)


solve()

計算量: 各フェーズの増加路本数 $O(E)$、フェーズ数 $O(\log U)$、BFS1回 $O(E)$。全体 $O(E^2\log U)$。

Step-by-Step 解説

1グラフ構築と初期Δの決定
順辺・逆辺を隣接リストに追加。$\Delta$ は最大容量以下の最大の2べき。

2Δ-残余グラフでのBFS増加路探索
残余容量が $\Delta$ 以上の辺のみ辿ってBFS。見つかったらボトルネック分だけ流す。

3フェーズの終了とΔの半減
増加路が尽きたら $\Delta$ を半分にする。$\Delta<1$ まで繰り返す。

4計算量の直感
各フェーズの増加路本数は $O(E)$ に抑えられ、$\Delta$ は $O(\log U)$ 回半減するため全体 $O(E^2\log U)$。

よくあるミス

ミス	原因	正しい書き方
$\Delta$ の初期値を1に固定	スケーリングの意味がなくなり通常のBFS法と同じ計算量になる	最大容量以下の最大の2べきから開始する
増加路が尽きた時点で全体を終了	Δをさらに半分にすればまだ流せる余地がある	Δを半減し $\Delta\ge1$ の間は継続する
BFSで残余容量チェックを `cap>0` にする	通常のBFS増加路探索と混同	Δ-残余グラフでは `cap>=delta` を条件にする
最大流の値がアルゴリズムで変わると誤解	最大流の値は経路選択に依存しない一意な最適値	Capacity Scalingの流量値は通常のFord-Fulkersonと必ず一致する

Day 098-Q4 — Capacity Scaling法（容量スケーリング法による最大流）

問題