Day 087-Q3 — Push-Relabel 法（プッシュ・リレーベル最大流）

問題

頂点数 $N$、辺数 $M$ の有向グラフが与えられる。各辺 $(u_i,v_i)$ には容量 $c_i$ がある。頂点 $S$ から頂点 $T$ への最大流量を求めよ。

入出力例

6 10 1 6
1 2 16
1 3 13
2 3 10
3 2 4
2 4 12
4 3 9
3 5 14
5 4 7
4 6 20
5 6 4

23

概念図: 高さラベルに沿って余剰を押し出す

ヒント

# current-arc ポインタ cur[u] で隣接辺を順に見る
# height[u]==height[v]+1 かつ残余容量>0 なら push
# 押せる辺がなければ relabel して cur[u]=0 にリセット

模範解答

import sys
from collections import deque

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

    graph = [[] for _ in range(n)]
    for _ in range(m):
        u = int(data[idx]) - 1; idx += 1
        v = int(data[idx]) - 1; 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])

    height = [0] * n
    excess = [0] * n
    height[s] = n
    cur = [0] * n
    active = deque()
    in_queue = [False] * n

    def try_enqueue(v):
        if v != s and v != t and not in_queue[v] and excess[v] > 0:
            active.append(v)
            in_queue[v] = True

    def push(u, e):
        v, cap, rev = graph[u][e]
        d = min(excess[u], cap)
        graph[u][e][1] -= d
        graph[v][rev][1] += d
        excess[u] -= d
        excess[v] += d
        try_enqueue(v)

    def relabel(u):
        mh = None
        for v, cap, rev in graph[u]:
            if cap > 0 and (mh is None or height[v] < mh):
                mh = height[v]
        if mh is not None:
            height[u] = mh + 1

    for e in range(len(graph[s])):
        v, cap, rev = graph[s][e]
        if cap > 0:
            graph[s][e][1] -= cap
            graph[v][rev][1] += cap
            excess[s] -= cap
            excess[v] += cap
            try_enqueue(v)

    while active:
        u = active.popleft()
        in_queue[u] = False
        while excess[u] > 0:
            if cur[u] == len(graph[u]):
                relabel(u)
                cur[u] = 0
            else:
                v, cap, rev = graph[u][cur[u]]
                if cap > 0 and height[u] == height[v] + 1:
                    push(u, cur[u])
                else:
                    cur[u] += 1

    print(excess[t])

solve()

計算量: $O(V^2E)$（一般的な push-relabel の理論上界。highest-label + gap ヒューリスティックで $O(V^2\sqrt{E})$ に改善可能）。

Step-by-Step 解説

Step 1: 残余グラフの構築

各辺に順辺（容量 $c$）と逆辺（容量 $0$）をペアで持たせ、push のたびに順辺を減らし逆辺を増やす。

Step 2: 前処理流の初期化

$\text{height}[S]=N$ とし $S$ から出る辺を容量いっぱいまで流す。隣接頂点に余剰が発生し active キューに積まれる。

Step 3: push と relabel

active な頂点を discharge：current-arc ポインタで隣接辺を順に走査し admissible なら push、そうでなければポインタを進める。全辺を見ても押せなければ relabel。

Step 4: 終了条件と答え

active キューが空になれば $S,T$ 以外の余剰はすべて $0$。$\text{excess}[T]$ が最大流量。

よくあるミス

次のステップ

• 発展問題: highest-label 選択 + gap ヒューリスティックで $O(V^2\sqrt{E})$ に高速化
• 発展問題: Dinic 法との実行時間比較（疎グラフ・密グラフ）

自己評価