Day 125-Q3 | Dinic法の最大流とLink-Cut Treeによる高速化理論

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺には容量がある。頂点 $S$ から頂点 $T$ への最大流を Dinic 法で求めよ。

入力形式

N M S T
u_1 v_1 cap_1
...
u_M v_M cap_M

制約

$1 \le N \le 500$

$0 \le M \le 3000$

$0 \le S,T \le N-1,\ S\neq T$

$1 \le cap_i \le 10^9$

多重辺・自己ループなし

入出力例

入力例1

出力例1

0→1→3に6、0→2→3に2、0→1→2→3に4流すと合計12。カット{0}と{1,2,3}の容量和10+2=12が最小カットと一致

入力例2

2 1 0 1
0 1 5

出力例2

概念図

ヒント（段階的開示）

ヒント1（方向性）

Ford-Fulkerson法（DFSで増加路を1本ずつ探す）は最悪計算量が大きくなりうる。Dinic法はこれを、フェーズという単位でまとめて多くの増加路を一度に流すことで高速化する。1フェーズは「BFSでレベルグラフを作る」「レベルグラフ上でDFSにより増加路を複数本まとめて流す（ブロッキングフロー）」の2段階からなる。

ヒント2（アプローチ）

BFSで各頂点に $S$ からの最短距離（レベル）を割り振り、レベルが1ずつ増加する辺だけを使うレベルグラフを作る。このレベルグラフ上で、これ以上増加路が引けなくなるまでDFSで流せるだけ流す（ブロッキングフロー）。1回のブロッキングフロー構築が終わったら再度BFSでレベルグラフを作り直す、という操作を $T$ に到達できなくなるまで繰り返す。フェーズ数は高々 $O(V)$、各フェーズは素朴なDFSで $O(VE)$ かかるため全体 $O(V^2E)$ となる。

ヒント3（誘導）

DFSでは「今の頂点から使える辺のイテレータ」を頂点ごとに保持し、一度使い切った辺は次から読み飛ばす（it 配列によるポインタ管理）ことで、1回のブロッキングフロー構築が償却 $O(VE)$ で終わるようにする。

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

模範解答 (Python)

import sys
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(self, s, t):
        level = [-1] * self.n
        level[s] = 0
        dq = deque([s])
        while dq:
            u = dq.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
                    dq.append(v)
        return level

    def dfs(self, u, t, f, level, it):
        if u == t:
            return f
        while it[u] < len(self.graph[u]):
            eid = self.graph[u][it[u]]
            v = self.to[eid]
            if self.cap[eid] > 0 and level[v] == level[u] + 1:
                d = self.dfs(v, t, min(f, self.cap[eid]), level, it)
                if d > 0:
                    self.cap[eid] -= d
                    self.cap[eid ^ 1] += d
                    return d
            it[u] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            level = self.bfs(s, t)
            if level[t] < 0:
                return flow
            it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'), level, it)
                if f == 0:
                    break
                flow += f


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

    mf = MaxFlow(n)
    for _ in range(m):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        mf.add_edge(u, v, c)

    print(mf.max_flow(s, t))


sys.setrecursionlimit(10000)
solve()

Step-by-Step 解説

1レベルグラフの構築（BFS）
$S$ からの最短距離（辺数）を全頂点に対してBFSで計算し、level[v] == level[u] + 1 を満たす辺だけを残した部分グラフ（レベルグラフ）を考える。レベルグラフ上の任意の $S \to T$ パスは、元のグラフにおける最短増加路になっている。

2ブロッキングフロー（DFS）
レベルグラフ上でDFSにより増加路を見つけて流す。容量が尽きた辺は使えなくなるので it ポインタを進めて次を探す。これを $S$ から $T$ へのパスがレベルグラフ上に存在しなくなるまで繰り返すことで、「レベルグラフ上でこれ以上流せない」状態（ブロッキングフロー）を作る。

3フェーズを繰り返す
ブロッキングフローを1つ作るたびに、$T$ までの最短距離は真に増加する。最短距離は高々 $V-1$ なので、フェーズ数は $O(V)$ に抑えられる。

4計算量 $O(V^2E)$ の内訳
1フェーズあたり：BFSが $O(E)$、DFSによるブロッキングフロー構築は償却 $O(VE)$。フェーズ数が $O(V)$ なので合計 $O(V \cdot VE) = O(V^2 E)$。

5Link-Cut Tree によるブロッキングフロー高速化（理論）
Link-Cut Tree（LCT）を使うと、レベルグラフを動的な森として管理し、「現在のパス上の最小容量辺」を $O(\log V)$ で取得し、その辺の容量ぶんだけパス全体の容量を一括で減算、容量が0になった辺は木からカットという操作を全て $O(\log V)$ で行える。1フェーズで発生するカット・リンクの回数は高々 $O(E)$ であるため、1フェーズ全体が $O(E \log V)$ で完了し、全体 $O(VE \log V)$ となる（Sleator & Tarjan, 1983）。

よくあるミス

ミス	原因	正しい書き方
`it` ポインタをDFSの再帰呼び出しごとにリセットしてしまう	1フェーズ内での状態共有を誤解	`it` は1回のブロッキングフロー構築を通して頂点ごとに保持し、リセットしない
逆辺の容量を初期化し忘れる	残余グラフの概念の理解不足	逆辺は容量0で追加し、流したぶんだけ増加させる
レベルグラフの条件を `level[v] > level[u]` のように緩くしてしまう	最短性を保証する条件の理解不足	必ず `level[v] == level[u] + 1` の等号条件にする
再帰DFSで最大再帰深度を超えてエラーになる	$N$ が大きいときの再帰上限を考慮していない	`sys.setrecursionlimit` を適切に設定するか反復DFSに書き換える

次のステップ

発展: 単位容量グラフ（二部マッチングなど）に限定すると、Dinic法は $O(E\sqrt V)$ に改善される（Hopcroft-Karpと同じ計算量オーダー）。
次回予告: 次点全域木（Second Best MST）・Kruskal法 + 二分累乗によるパス最大辺クエリ

自己評価

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

Day 125-Q3 — Dinic法の最大流とLink-Cut Treeによる高速化理論

問題