Day 091-Q2 — 最小費用流（MCMF・ポテンシャル法 Dijkstra）

問題

$N$ 頂点 $M$ 辺の有向グラフ（各辺に容量 $\mathrm{cap}$・単位コスト $\mathrm{cost}\ge0$）で、頂点 $1$ から $N$ への最大流量と、それを達成する最小総コストを求める。

入出力例

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

3 10

最安路から順に $1\to2\to3\to4$(3), $1\to3\to4$(3), $1\to2\to4$(4) で合計10。

概念図

ヒント

# ポテンシャル法（Johnson 変換）
reduced = cost + h[u] - h[v]   # >= 0 が保証
# 1回の最短路後に h[v] += dist[v]
total_cost += f * h[t]         # h[t] が実距離

模範解答

import sys
import heapq

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

    # graph[u] = list of [to, cap, cost, rev_index]
    graph = [[] for _ in range(n + 1)]
    def add_edge(u, v, cap, cost):
        graph[u].append([v, cap, cost, len(graph[v])])
        graph[v].append([u, 0, -cost, len(graph[u]) - 1])

    for _ in range(m):
        u = int(data[idx]); v = int(data[idx+1])
        cap = int(data[idx+2]); cost = int(data[idx+3]); idx += 4
        add_edge(u, v, cap, cost)

    s, t = 1, n
    INF = float('inf')
    total_flow = 0
    total_cost = 0
    h = [0] * (n + 1)   # ポテンシャル（初期コスト非負なので0でよい）

    while True:
        dist = [INF] * (n + 1)
        dist[s] = 0
        prevv = [-1] * (n + 1)
        preve = [-1] * (n + 1)
        pq = [(0, s)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for i, e in enumerate(graph[u]):
                v, cap, cost, _ = e
                if cap > 0:
                    nd = d + cost + h[u] - h[v]   # 補正済みコスト >= 0
                    if nd < dist[v]:
                        dist[v] = nd
                        prevv[v] = u
                        preve[v] = i
                        heapq.heappush(pq, (nd, v))
        if dist[t] == INF:
            break   # これ以上流せない → 最大流に到達
        for v in range(1, n + 1):
            if dist[v] < INF:
                h[v] += dist[v]
        # 増加路のボトルネック容量を求める
        f = INF
        v = t
        while v != s:
            f = min(f, graph[prevv[v]][preve[v]][1])
            v = prevv[v]
        # 流す（順辺を減らし逆辺を増やす）
        v = t
        while v != s:
            e = graph[prevv[v]][preve[v]]
            e[1] -= f
            graph[v][e[3]][1] += f
            v = prevv[v]
        total_flow += f
        total_cost += f * h[t]   # h[t] は s->t の実際の最短コスト

    print(total_flow, total_cost)

main()

Step-by-Step 解説

Step 1: 残余グラフの表現

順辺 [v,cap,cost,rev] と逆辺 [u,0,-cost,rev] を張る。rev で逆辺容量を更新する。

Step 2: ポテンシャルで負辺を消す

補正コスト $\mathrm{cost}+h[u]-h[v]$ は三角不等式から非負が保証され Dijkstra が使える。

Step 3: 最短路に沿って流す

$s\to t$ 最短路の最小残余容量 $f$ を流し、順辺を $f$ 減らし逆辺を $f$ 増やす。

Step 4: ポテンシャル更新と総コスト加算

各頂点で $h[v] \mathrel{+}= \mathrm{dist}[v]$。実距離は $h[t]$ に一致し total_cost += f*h[t]。到達不能になれば最大流に到達し終了。

よくあるミス

次のステップ

• 発展: 「ちょうど $F$ 単位流す最小費用」に変更
• 発展: 負辺を含む場合の初回 Bellman-Ford 初期化
• 次回予告: Aho-Corasick + オートマトンDP

自己評価