Day 136-Q3 | ZKW法（最小費用最大流）

問題

$N$ 頂点 $M$ 辺の有向グラフがある。各辺には容量 $c$ とコスト $w$（1単位の流量を流すのにかかる費用）が設定されている。頂点 $S$ から頂点 $T$ への最大流量を求め、その最大流量を実現する流し方の中で総費用が最小となる値を求めよ。

SPFA（キューを使ったベルマン・フォード法）で最短距離のレイヤーを求め、その距離が確定した辺だけを使ってDFSで複数の増加路を一括に流す「ZKW法」で実装せよ。

入力形式

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

制約

$2 \le N \le 300$

$1 \le M \le 2000$

$1 \le c_i \le 100$

$0 \le w_i \le 1000$

負閉路は存在しない

入出力例

入力例1

出力例1

4 16

概念図

ヒント（段階的開示）

ヒント1（方向性）

「最大流をまず求めてからコストを最小化する」のではなく、「常に現時点で最短（最小コスト）な増加路から使う」という貪欲を繰り返すと、結果として最大流かつ最小費用になる。残余辺に負コストが現れるため、Dijkstra単体では扱えない。

ヒント2（アプローチ）

SPFAでdist[]を求め、dist[v]==dist[u]+cost(u,v)を満たす辺だけを残した「最短路DAG」を作る。このDAG上でDFSを行い、1回のフェーズで複数の増加路をまとめて流し切ってから次のSPFAに進む。これがDinic法のブロッキングフローに相当する「DFS一括拡張」。

ヒント3（誘導）

def dfs(u, pushed, dist, visited):
    if u == T:
        return pushed
    visited[u] = True
    result = 0
    for eid in graph[u]:
        v = to[eid]
        if not visited[v] and cap[eid] > 0 and dist[v] == dist[u] + cost[eid]:
            d = dfs(v, min(pushed - result, cap[eid]), dist, visited)
            if d > 0:
                cap[eid] -= d
                cap[eid ^ 1] += d
                result += d
                if result == pushed:
                    break
    return result

辺を「順辺・逆辺」のペアとして偶数・奇数番目に追加するとeid^1で対応する逆辺を即座に求められる。

模範解答 (Python)

import sys
from collections import deque


def main():
    data = sys.stdin.buffer.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

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

    def add_edge(u, v, c, w):
        graph[u].append(len(to))
        to.append(v); cap.append(c); cost.append(w)
        graph[v].append(len(to))
        to.append(u); cap.append(0); cost.append(-w)

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

    INF = float("inf")
    sys.setrecursionlimit(1 << 20)

    def spfa():
        dist = [INF] * (N + 1)
        in_queue = [False] * (N + 1)
        dist[S] = 0
        dq = deque([S])
        in_queue[S] = True
        while dq:
            u = dq.popleft()
            in_queue[u] = False
            for eid in graph[u]:
                if cap[eid] > 0 and dist[u] + cost[eid] < dist[to[eid]]:
                    dist[to[eid]] = dist[u] + cost[eid]
                    v = to[eid]
                    if not in_queue[v]:
                        in_queue[v] = True
                        dq.append(v)
        return dist

    def dfs(u, pushed, dist, visited):
        if u == T:
            return pushed
        visited[u] = True
        result = 0
        for eid in graph[u]:
            v = to[eid]
            if (not visited[v]) and cap[eid] > 0 and dist[v] == dist[u] + cost[eid]:
                d = dfs(v, min(pushed - result, cap[eid]), dist, visited)
                if d > 0:
                    cap[eid] -= d
                    cap[eid ^ 1] += d
                    result += d
                    if result == pushed:
                        break
        return result

    total_flow = 0
    total_cost = 0

    while True:
        dist = spfa()
        if dist[T] == INF:
            break
        while True:
            visited = [False] * (N + 1)
            f = dfs(S, INF, dist, visited)
            if f == 0:
                break
            total_flow += f
            total_cost += f * dist[T]

    print(total_flow, total_cost)


main()

Step-by-Step 解説

1なぜSPFAが必要か
残余グラフには逆辺として負コスト辺が出現する。ポテンシャル補正なしでは Dijkstra は壊れるため、SPFA（負辺対応のベルマン・フォード＋キュー高速化）を使う。

2最短路DAG上だけをDFS
dist[v]==dist[u]+cost[eid]で辺を絞り込むと、そのフェーズで1単位あたりのコストがdist[T]一定になる。

3DFS一括拡張（ZKWの核心）
1回のSPFAで得たDAGに対しDFSをf==0になるまで繰り返し、そのレイヤーで流せるだけ使い切ってから次のSPFAへ進む。

4visitedをフェーズごとにリセット
初期化しないと別の増加路で使った頂点を経由できず、流量を取りこぼす。

5フェーズ終了条件
dist[T]==INFで$S$から$T$へ到達不能になったら最大流に達した合図。

よくあるミス

ミス	原因	正しい書き方
Dijkstraで残余グラフの最短路を求めてしまう	逆辺の負コストを扱えない	素直にSPFA（ベルマン・フォード）を使う
visitedをフェーズをまたいで使い回す	別フェーズで到達できる頂点をスキップしてしまう	各dfs呼び出し前にvisitedを初期化する
pushedの初期値を小さい定数にする	流量の上限を不必要に制限してしまう	INFを初期pushedとして渡す
逆辺のインデックス計算を誤る	辺の追加順序がずれeid^1が対応しない	順辺・逆辺を必ず連続する2インデックスで追加
コストの符号を取り違える	逆辺のコストを+wにしてしまう	逆辺のコストは必ず-w

次のステップ

発展: 「流量をちょうど$F$に固定した場合の最小費用」に拡張し、$F$が最大流を超える場合の扱いを検討せよ。
発展2: SPFAの代わりにポテンシャルを維持したDijkstra（プライマル・デュアル法）に書き換え性能比較せよ。

自己評価

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

Day 136-Q3 — ZKW法（SPFA距離レイヤ + DFS一括拡張）

問題