Day 140-Q3 | Capacity Scaling Maximum Flow

問題

$N$ 頂点 $M$ 辺の有向グラフがあり、各辺には容量が定められている。始点 $s$ から終点 $t$ への最大流を求めよ。

素朴な Ford-Fulkerson 法は容量が大きい場合に増加路の本数が容量に比例して増えうるため非効率になりうる。これを防ぐのがCapacity Scaling（容量スケーリング）法である。

全辺の最大容量を$C$とし、$\Delta$を$2^k\le C$を満たす最大の2冪から開始する
現在の$\Delta$について、「残余容量が$\Delta$以上の辺だけ」を使って$s\to t$のBFS増加路を探し、見つかる限り繰り返しフローを流す
これ以上$\Delta$以上の残余容量を持つ増加路が見つからなくなったら、$\Delta$を半分にして手順2に戻る
$\Delta<1$になったら終了し、総フロー量を出力する

入力形式

N M s t
u_1 v_1 c_1
:
u_M v_M c_M

制約

$2 \le N \le 500$

$0 \le M \le 3000$

$1 \le c_i \le 10^6$

多重辺の可能性あり

入出力例

入力例1

出力例1

入力例2

出力例2

概念図

ヒント（段階的開示）

ヒント1（方向性）

増加路を「見つかったら1本ずつ流す」という発想自体は素朴なFord-Fulkerson法と同じである。違いは「どの増加路を優先的に選ぶか」にある。容量の大きい辺だけを使う増加路を先に処理してしまえば、少ない本数のフロー更新で大きな流量を稼げる、という直感がベースになっている。

ヒント2（アプローチ）

$\Delta$を「今のフェーズで許容する最小残余容量」として固定し、残余グラフから「残余容量が$\Delta$未満の辺」を取り除いた部分グラフの上でBFSを行う。このBFSで見つかる増加路は、必ずボトルネックが$\Delta$以上になる。$\Delta$が尽きるまでこのフェーズを繰り返してから$\Delta$を半分にすることで、「大きい流量を稼げる増加路から先に処理する」ことを保証する。

ヒント3（誘導）

def bfs_delta(delta):
    # 残余容量 >= delta の辺だけを使ってs->tへのBFS増加路を探す
    # 見つかったらボトルネック分だけ流し、その量を返す。なければ0
    ...

max_cap = 全辺の容量の最大値
delta = max_cap を超えない最大の2冪
flow = 0
while delta >= 1:
    while True:
        f = bfs_delta(delta)
        if f == 0:
            break
        flow += f
    delta //= 2
print(flow)

模範解答 (Python)

import sys
from collections import deque

def main():
    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)]
    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])

    def bfs_delta(delta):
        prevv = [-1] * n
        preve = [-1] * n
        visited = [False] * n
        visited[s] = True
        q = deque([s])
        while q:
            u = q.popleft()
            if u == t:
                break
            for i, e in enumerate(graph[u]):
                v, cap, rev = e
                if not visited[v] and cap >= delta:
                    visited[v] = True
                    prevv[v] = u
                    preve[v] = i
                    q.append(v)
        if not visited[t]:
            return 0
        d = float('inf')
        v = t
        while v != s:
            u = prevv[v]
            i = preve[v]
            d = min(d, graph[u][i][1])
            v = u
        v = t
        while v != s:
            u = prevv[v]
            i = preve[v]
            graph[u][i][1] -= d
            rev = graph[u][i][2]
            graph[v][rev][1] += d
            v = u
        return d

    max_cap = 0
    for u in range(n):
        for e in graph[u]:
            max_cap = max(max_cap, e[1])

    flow = 0
    if max_cap > 0:
        delta = 1
        while delta * 2 <= max_cap:
            delta *= 2
        while delta >= 1:
            while True:
                f = bfs_delta(delta)
                if f == 0:
                    break
                flow += f
            delta //= 2

    print(flow)

main()

Step-by-Step 解説

1フェーズの構造
$\Delta$の値ごとに「増加路がなくなるまで流す」という小さなFord-Fulkersonをネストして実行する。$\Delta$は$C,C/2,\dots,1$と$O(\log C)$回だけ半分にされる。

2各フェーズの増加路本数がO(M)で抑えられる理由
$\Delta$-フェーズ終了時点から$\Delta$を半分にすると、新フェーズで見つかる各増加路のボトルネックは$[\Delta/2,\Delta)$の範囲に収まる。カット容量の議論から、次フェーズで流せる増加路の本数は$O(M)$本に抑えられる。

3全体計算量
フェーズ数$O(\log C)$、各フェーズの増加路本数$O(M)$、各増加路をBFSで見つけるのに$O(M)$かかるので全体で$O(M^2\log C)$。

4なぜ通常のFord-Fulkersonより速いのか
通常のFord-Fulkersonは悪い辺選択をすると小さな辺1本に律速され最悪$O(F)$回のBFSが必要になる。容量スケーリングは序盤で大きな流量を一気に稼ぎ、終盤でも1フェーズあたり$O(M)$本に抑えられるため、流量の絶対値に依存しない多項式時間が保証される。

5サンプルの検算
入力例1はCLRSの教科書に頻出の6頂点ネットワークで最大流量は23。入力例2は複数経路の組み合わせで計5まで流せる小規模な例。

よくあるミス

ミス	原因	正しい書き方
BFSの探索条件を`cap > 0`のままにしてしまう	Edmonds-Karpのコードをそのまま流用	`cap >= delta`を条件にする
Δの初期値を1から開始してしまう	スケーリングの発想を忘れる	最大容量を超えない最大の2冪から開始し半分にしながら減らす
Δが0になった後もループを続けてしまう	終了条件を書き忘れる	`while delta >= 1`として確実に抜ける
各フェーズで増加路を1本しか流さず次のΔに進む	フェーズ内ループを書き忘れる	同じΔで見つからなくなるまで繰り返し流し切る
逆辺の残余容量更新を忘れる	残余グラフの逆辺構築を省略	順辺追加時に容量0の逆辺も同時に追加する

次のステップ

発展: Dinic法（ブロッキングフロー）で解き直し、実行時間・増加路の総本数を比較せよ。密グラフと疎グラフでどちらが有利か実測で確認せよ。
発展2: 最小費用流に拡張した「容量スケーリング + 最短路」のアルゴリズムを実装し、単純な逐次最短増加路法とのフェーズ数の違いを比較せよ。

自己評価

完全理解おおむね理解要復習

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

問題