Day 106-Q2 | ISAP（最大流）

問題

$N$頂点$M$辺の有向グラフが与えられる。各辺$i$は$u_i\to v_i$の容量$c_i$の辺。頂点$S$から$T$への最大流量を求めよ。

ISAP（Improved Shortest Augmenting Path）は、各頂点に「$T$への残余グラフ上の最短距離の下界」$\mathrm{dist}(v)$を保持し、$\mathrm{dist}(u)=\mathrm{dist}(v)+1$を満たす辺だけを辿って前進する。行き詰まったら距離ラベルを再計算（relabel）する。さらに、ある距離値を持つ頂点が0個になった瞬間$S$-$T$間の遮断が確定するGap最適化を組み合わせることで$O(V^2E)$を達成する。

入力形式

N M
S T
u_1 v_1 c_1
...
u_M v_M c_M

制約

$2 \le N \le 2000$

$1 \le M \le 10000$

$1 \le S,T \le N,\ S\ne T$

$1 \le c_i \le 10^9$

多重辺・逆向き平行辺あり

入出力例

入力例1

出力例1

$1\to2\to4$に2、$1\to3\to4$に2、残った$1\to2$の容量1を$2\to3\to4$経由で1流し合計5が最大流。

概念図: 距離ラベルとGap最適化

ヒント（段階的開示）

ヒント1: 方向性

BFSで見つけた最短増加路を1本ずつ流す素朴な実装でも正しいが遅い。「増加路探索のたびに毎回BFSをやり直す」のではなく、一度計算した距離ラベルを使い回し、行き詰まった頂点だけ部分的に修正（relabel）することで探索の手戻りを最小化するのがISAPの核心。

ヒント2: アプローチ

Tから逆向きBFSして各頂点のdist(v)（残余グラフ上のv→T最短ホップ数）を初期化する（残余辺v→uの存在は「u→vの逆辺の残余容量が正」で判定）。Sから出発しdist[u]==dist[v]+1を満たす辺だけを辿って前進。Tに着いたらボトルネック容量だけ流し容量が尽きた辺の直前まで戻る。前進できなければ隣接辺のdist(v)の最小値+1にdist(u)を更新（relabel）。gap配列である距離値の頂点数を数え、relabelでgap[旧距離]が0になったらS-T間の遮断が確定し打ち切る。

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

while dist[S] < N:
    if u == T:
        # 経路上のボトルネック容量だけ流す。
        # 最初に容量0になった辺の位置まで経路を切り詰める
        ...
    elif 前進できる辺がある(cap>0 かつ dist[v]+1==dist[u]):
        経路にvを積んでu = v
    else:
        gap[dist[u]] -= 1
        if gap[dist[u]] == 0: break  # 遮断確定
        dist[u] = 隣接辺から計算した新しい値
        gap[dist[u]] += 1
        if u != S: 経路を1つ戻す

模範解答 (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
    s = int(data[idx]) - 1; idx += 1
    t = int(data[idx]) - 1; idx += 1

    to = []
    cap = []
    head = [[] 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
        head[u].append(len(to)); to.append(v); cap.append(c)
        head[v].append(len(to)); to.append(u); cap.append(0)

    INF_D = n
    dist = [INF_D] * n
    gap = [0] * (n + 1)

    def bfs():
        for i in range(n):
            dist[i] = INF_D
        dist[t] = 0
        gap[:] = [0] * (n + 1)
        gap[0] = 1
        dq = deque([t])
        while dq:
            u = dq.popleft()
            for eid in head[u]:
                v = to[eid]
                if dist[v] == INF_D and cap[eid ^ 1] > 0:
                    dist[v] = dist[u] + 1
                    gap[dist[v]] += 1
                    dq.append(v)

    bfs()
    flow = 0
    if dist[s] != INF_D:
        it = [0] * n
        path_nodes = [s]
        path_edges = []
        u = s
        while dist[s] < n:
            if u == t:
                aug = min(cap[e] for e in path_edges)
                cut = len(path_edges)
                for i, e in enumerate(path_edges):
                    cap[e] -= aug
                    cap[e ^ 1] += aug
                    if cap[e] == 0 and cut == len(path_edges):
                        cut = i
                flow += aug
                del path_nodes[cut + 1:]
                del path_edges[cut:]
                u = path_nodes[-1]
                continue
            advanced = False
            adj = head[u]
            i = it[u]
            while i < len(adj):
                eid = adj[i]
                v = to[eid]
                if cap[eid] > 0 and dist[v] + 1 == dist[u]:
                    it[u] = i
                    path_nodes.append(v)
                    path_edges.append(eid)
                    u = v
                    advanced = True
                    break
                i += 1
            if not advanced:
                it[u] = len(adj)
                gap[dist[u]] -= 1
                if gap[dist[u]] == 0:
                    break
                mind = n
                for eid in adj:
                    v = to[eid]
                    if cap[eid] > 0 and dist[v] + 1 < mind:
                        mind = dist[v] + 1
                dist[u] = mind
                if dist[u] < n:
                    gap[dist[u]] += 1
                it[u] = 0
                if u == s:
                    if dist[s] >= n:
                        break
                    continue
                path_nodes.pop()
                path_edges.pop()
                u = path_nodes[-1]

    print(flow)


solve()

計算量: $O(V^2E)$（各relabelでdistは単調増加し高々$V$回、各頂点でのadvance/retreatの総回数は$O(VE)$）。ランダム300ケースでEdmonds-Karp相当のBFS最大流と一致することを確認済み。

Step-by-Step 解説

1逆BFSで初期距離ラベル
Tから「残余辺v→uが存在する」条件でBFS。未到達頂点はdist=N（番兵）のままにし、-1のような負の番兵は使わない。

2advance（前進）
cap>0かつdist[v]+1==dist[u]を満たすadmissibleな辺をcurrent arc it[u]から順に探す。同じ頂点の再訪で先頭から探し直す無駄を省く。

3retreat（relabel）とGap最適化
前進できなければ隣接辺のdist(v)+1の最小値に更新。直前にgap[旧dist]を減らし0になれば遮断確定で打ち切る。

4増加路発見時の巻き戻し
最初に容量0になった辺の位置まで経路を切り詰める。末尾だけを見ると無限ループの原因になる。

よくあるミス

ミス	原因	正しい書き方
未到達頂点のdistを-1にする	relabelの最小値計算で誤って「近い」と判定され無限ループ	未到達の番兵はN（あり得ない大きい値）にする
augment後の巻き戻しを最後の辺だけで判定	ボトルネック辺が経路途中の場合、流量0のaugmentを繰り返し無限ループ	先頭から走査し最初に容量0になった辺まで切り詰める
Gap最適化の判定をrelabel前に行う	減算前の値では消滅を正しく検出できない	gap[dist[u]]-=1の直後に0か確認する
relabel後にit[u]をリセットし忘れる	古い辺インデックスから再開すると新しいadmissible辺を見逃す	relabel後は必ずit[u]=0にする

次のステップ

発展: 最小費用最大流に拡張する（ポテンシャル付きダイクストラとの組合せ、Day105-Q1参照）
発展: Dinic法（ブロッキングフロー）と実測速度を同じグラフで比較する
次回予告: FKS完全ハッシュ法（2段階ユニバーサルハッシュによる最悪$O(1)$検索）

自己評価

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

Day 106-Q2 — ISAP（Improved Shortest Augmenting Path）

問題