Day 086-Q2 — Dinic 法 最大流（レベルグラフ + ブロッキングフロー・$O(V^2 E)$）

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺は容量 $c$ を持つ。始点 $S$ から終点 $T$ への最大流量を求めよ。

入出力例

4 5 0 3
0 1 2
0 2 1
1 2 1
1 3 1
2 3 2

3

$0\to1\to3$、$0\to2\to3$、$0\to1\to2\to3$ の 3 経路で合計 3 流せる。

概念図: レベルグラフとブロッキングフロー

ヒント

while bfs(s, t):
    it = [0]*n
    while (f := dfs(s, t, INF)) > 0:
        flow += f

模範解答

import sys
from collections import deque
sys.setrecursionlimit(1 << 20)

class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]
    def add_edge(self, u, v, c):
        self.g[u].append([v, c, len(self.g[v])])
        self.g[v].append([u, 0, len(self.g[u]) - 1])
    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, c, _ in self.g[u]:
                if c > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0
    def dfs(self, u, t, f):
        if u == t:
            return f
        while self.it[u] < len(self.g[u]):
            e = self.g[u][self.it[u]]
            v, c, rev = e
            if c > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(f, c))
                if d > 0:
                    e[1] -= d
                    self.g[v][rev][1] += d
                    return d
            self.it[u] += 1
        return 0
    def max_flow(self, s, t):
        flow = 0
        INF = float('inf')
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, INF)
                if f == 0:
                    break
                flow += f
        return flow

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); S = int(data[idx+2]); T = int(data[idx+3]); idx += 4
    din = Dinic(N)
    for _ in range(M):
        u = int(data[idx]); v = int(data[idx+1]); c = int(data[idx+2]); idx += 3
        din.add_edge(u, v, c)
    print(din.max_flow(S, T))

solve()

計算量: $O(V^2 E)$。単位容量（二部マッチング等）では $O(E\sqrt V)$。

Step-by-Step 解説

Step 1: 残余グラフの表現

各辺を [to, cap, rev]、逆辺を容量 0 で同時に張る。流したら正辺を減らし逆辺を増やす。

Step 2: レベルグラフ (BFS)

始点から BFS で層 level を求める。終点に到達不能なら終了。

Step 3: ブロッキングフロー (DFS)

level[v]==level[u]+1 の辺のみ辿り複数経路をまとめて流す。it で行き止まりの辺を再訪しない。

Step 4: フェーズ反復

1 回の BFS + 複数 DFS で 1 フェーズ。層数は真に増えるため最大 $V$ フェーズ。

よくあるミス

次のステップ

• 発展問題: 最小カット復元（残余グラフで $S$ から到達可能な頂点集合）
• 発展問題: 二部マッチング最大化（左右頂点を $S,T$ に接続し単位容量）

自己評価