Day 121-Q2 | Push-Relabel法（Preflow-Push + Gap Heuristic）

問題

N頂点M辺の有向グラフがあり、各辺には容量が定められている。頂点1を始点（source）、頂点Nを終点（sink）として、始点から終点への最大流量を求めよ。

入力形式

N M
u_1 v_1 c_1
...
u_M v_M c_M

制約

$2 \le N \le 1000$

$0 \le M \le 5000$

$1 \le c \le 10^4$

同一(u,v)が複数回現れる場合あり

入出力例

入力例1

出力例1

この例はCLRSの教科書にも登場する古典的なネットワーク。最小カット {1}|{2,3,4} の容量10+5=15が最大流と一致する。

概念図: 高さ関数と push / relabel

ヒント（段階的開示）

ヒント1: 方向性

Dinic法は「増加パスを見つけては流す」という発想だが、Push-Relabel法は逆に「まず過剰に流し込んでおいて、後から辻褄を合わせる」という発想に立つ。各頂点に高さ（height）という概念を導入し、水が高いところから低いところへ流れるように局所的な操作だけで流量を押し出していく。

ヒント2: アプローチ

各頂点$v$に余剰流量excess[v]と高さh[v]を持たせる。始点の高さを$N$、他をすべて$0$に初期化し、始点からすべての隣接辺を容量いっぱいまで流す（プレフロー）。あとはpush（$h[u]=h[v]+1$を満たす残余辺への押し出し）とrelabel（pushできる辺がなければ高さを引き上げる）を繰り返す。Gap Heuristicは、ある高さにちょうど1頂点しかいなくなった瞬間、それより高い頂点をまとめて非アクティブにする高速化。

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

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

def relabel(u):
    height[u] = min(height[v] for v, cap, _ in graph[u] if cap > 0) + 1

# アクティブ頂点(excess>0かつsource/sink以外)がなくなるまでpush/relabelを繰り返す

模範解答 (Python)

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

    graph = [[] for _ in range(N + 1)]

    def add_edge(u, v, cap):
        graph[u].append([v, cap, len(graph[v])])
        graph[v].append([u, 0, len(graph[u]) - 1])

    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        c = int(data[idx]); idx += 1
        add_edge(u, v, c)

    S, T = 1, N

    height = [0] * (N + 1)
    excess = [0] * (N + 1)
    height_count = [0] * (2 * N + 2)
    active_by_height = [deque() for _ in range(2 * N + 2)]
    in_active = [False] * (N + 1)

    height[S] = N
    height_count[0] = N - 1
    height_count[N] += 1

    cur = [0] * (N + 1)

    def enqueue(v):
        if v != S and v != T and excess[v] > 0 and not in_active[v] and height[v] < 2 * N:
            in_active[v] = True
            active_by_height[height[v]].append(v)

    for i, e in enumerate(graph[S]):
        v, cap, rev = e
        if cap > 0:
            graph[v][rev][1] += cap
            excess[S] -= cap
            excess[v] += cap
            graph[S][i][1] = 0
            enqueue(v)

    def gap(h):
        for v in range(1, N + 1):
            if v != S and h < height[v] < N:
                height_count[height[v]] -= 1
                height[v] = max(height[v], N + 1)
                height_count[height[v]] += 1

    cur_height = 0
    while cur_height <= 2 * N:
        if not active_by_height[cur_height]:
            cur_height += 1
            continue
        u = active_by_height[cur_height].popleft()
        in_active[u] = False
        if excess[u] <= 0 or u == S or u == T:
            continue

        while excess[u] > 0:
            if cur[u] == len(graph[u]):
                old_h = height[u]
                min_h = None
                for v, cap, rev in graph[u]:
                    if cap > 0:
                        if min_h is None or height[v] < min_h:
                            min_h = height[v]
                if min_h is None:
                    break
                height_count[old_h] -= 1
                height[u] = min_h + 1
                height_count[height[u]] += 1
                if height_count[old_h] == 0 and old_h < N:
                    gap(old_h)
                cur[u] = 0
                cur_height = height[u]
            else:
                v, cap, rev = graph[u][cur[u]]
                if cap > 0 and height[u] == height[v] + 1:
                    delta = min(excess[u], cap)
                    graph[u][cur[u]][1] -= delta
                    graph[v][rev][1] += delta
                    excess[u] -= delta
                    excess[v] += delta
                    enqueue(v)
                    if excess[u] == 0:
                        break
                else:
                    cur[u] += 1
        if excess[u] > 0 and height[u] <= 2 * N:
            active_by_height[height[u]].append(u)
            in_active[u] = True
            cur_height = height[u]
        else:
            cur_height = 0

    print(excess[T])


solve()

計算量: 基本形のPush-Relabel法は $O(V^2E)$。Gap Heuristicを併用すると実測で大幅な高速化が見込め、FIFO選択規則との組み合わせで $O(V^3)$ 保証も知られる。CLRS掲載の古典例（4頂点5辺、最大流15）で手計算・実装ともに一致することを確認済み。

Step-by-Step 解説

1プレフローという発想の転換
Ford-Fulkerson系は流量保存則を常に満たしながら増やしていくが、Push-Relabel法は一時的に「流入>流出」の頂点（余剰）を許容するプレフローを扱う。全頂点で余剰が0になれば最大流に等しい。

2高さ関数が流れの向きを決める
各頂点に高さh[v]を割り当て、余剰は高いところから低いところへしか流さない。始点の高さをNに固定する。

3pushとrelabelの2操作
h[u]=h[v]+1を満たす残余辺があればpush、なければ行き先の高さの最小値+1までh[u]を引き上げる（relabel）。

4current-arc pointerで無駄走査を削減
各頂点に「前回どこまで調べたか」のポインタを持たせ、relabelが起きたときだけリセットする。

5Gap Heuristicによる高速化
ある高さの頂点が0個になった瞬間、それより高い頂点をまとめて非アクティブな高さに引き上げ、無意味な試行を削減する。

よくあるミス

ミス	原因	正しい書き方
高さの初期値をソース以外すべて0にし忘れる	Dinic法のレベルグラフと混同する	height[S]=N、他は0で初期化しプレフローを流す
relabel後にcurrent-arcポインタをリセットしない	一度調べた辺はもう調べなくてよいと誤解する	relabelのたびにcur[u]=0に戻す
excess[T]ではなくexcess[S]の変化量を答えにしてしまう	フローの向きの直感と実装が食い違う	終了後のexcess[T]がそのまま最大流量になる
Gap Heuristicの適用範囲をN未満に限定しない	全高さ帯にheight_countを適用してしまう	height<Nの頂点だけを対象にgap処理する

次のステップ

発展: FIFO選択規則やHighest-Label選択規則との計算量比較を実測してみる。
次回予告: Y-fast Trie（successor/predecessorをO(log log U)で処理する確率的データ構造）

自己評価

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

Day 121-Q2 — Push-Relabel法（Preflow-Push + Gap Heuristic）

問題