Day 037-Q5 | 最小費用流（負辺対応 Johnson + 繰り返し最短路）

問題

$V$ 頂点 $E$ 辺の有向グラフで、各辺は容量 $c \ge 0$・コスト $d$（負を含む）。$s \to t$ への流量 $F$ の最小費用流コストを求める。流せない場合 -1。負閉路は無いことが保証される。

制約

$2 \le V \le 1000$

$1 \le E \le 5000$

$1 \le F \le 10^6$

$0 \le c \le 10^4$, $-10^4 \le d \le 10^4$

入出力例

入力例 1

出力例 1

概念図: Johnson ポテンシャル変換

初回 Bellman-Ford で得たポテンシャル $h$ を使い、残余コストを $d' = d + h[u] - h[v] \ge 0$ に変換。以降は Dijkstra で増路探索可能。

ヒント (段階的開示)

ヒント1: 方向性

負辺があると Dijkstra は直接使えない。初回 Bellman-Ford でポテンシャル $h$ を計算し、Johnson 変換で全辺非負化。

ヒント2: アプローチ

ループ:
1. 残余グラフ上 Dijkstra($s \to t$)、辺コストは $d + h[u] - h[v]$。
2. 経路があれば最小容量を流す。
3. h[v] += dist[v] でポテンシャル更新。
4. $F$ 流し切るまで繰り返し。

ヒント3: 残余グラフ実装

各順辺 $(u, v, c, d)$ に対し逆辺 $(v, u, 0, -d)$ を追加。rev_index で順・逆をペアリング。

graph[u].append([v, c, d, len(graph[v])])
graph[v].append([u, 0, -d, len(graph[u])-1])

模範解答 (Python)

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
INF = 10**18

class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
    def add_edge(self, u, v, cap, cost):
        self.graph[u].append([v, cap, cost, len(self.graph[v])])
        self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1])

    def bellman_ford(self, s):
        dist = [INF] * self.n
        dist[s] = 0
        for _ in range(self.n - 1):
            updated = False
            for u in range(self.n):
                if dist[u] == INF: continue
                for v, cap, cost, _ in self.graph[u]:
                    if cap > 0 and dist[u] + cost < dist[v]:
                        dist[v] = dist[u] + cost; updated = True
            if not updated: break
        return dist

    def min_cost_flow(self, s, t, F):
        n = self.n
        h = self.bellman_ford(s)
        for i in range(n):
            if h[i] == INF: h[i] = 0
        total = 0
        while F > 0:
            dist = [INF] * n
            prev_v = [-1] * n; prev_e = [-1] * n
            dist[s] = 0
            pq = [(0, s)]
            while pq:
                d, u = heappop(pq)
                if d > dist[u]: continue
                for i, (v, cap, cost, _) in enumerate(self.graph[u]):
                    if cap > 0:
                        nd = d + cost + h[u] - h[v]
                        if nd < dist[v]:
                            dist[v] = nd
                            prev_v[v] = u; prev_e[v] = i
                            heappush(pq, (nd, v))
            if dist[t] == INF:
                return -1
            for v in range(n):
                if dist[v] < INF:
                    h[v] += dist[v]
            d = F; v = t
            while v != s:
                e = self.graph[prev_v[v]][prev_e[v]]
                d = min(d, e[1])
                v = prev_v[v]
            v = t
            while v != s:
                e = self.graph[prev_v[v]][prev_e[v]]
                e[1] -= d
                self.graph[v][e[3]][1] += d
                v = prev_v[v]
            total += d * h[t]
            F -= d
        return total

def solve():
    V, E, F, s, t = map(int, input().split())
    mcf = MinCostFlow(V)
    for _ in range(E):
        u, v, c, d = map(int, input().split())
        mcf.add_edge(u, v, c, d)
    print(mcf.min_cost_flow(s, t, F))

solve()

Step-by-Step 解説

1残余グラフ構築
順辺 $(u,v,c,d)$ + 逆辺 $(v,u,0,-d)$。逆辺を「フローの戻し」に使用。

2初回 Bellman-Ford
負辺があるので Dijkstra は不可。$s$ からの最短距離 $h$ を $O(VE)$ で計算。

3Johnson 変換
辺コストを $d'(u,v) = d + h[u] - h[v] \ge 0$ に変換。最短路構造は不変。

4Dijkstra で増路探索
$s \to t$ の最短路を heap で $O(E \log V)$。

5増路フロー
経路上の最小容量を流す。逆辺の cap 増、順辺の cap 減。

6ポテンシャル更新
$h[v] \mathrel{+}= \text{dist}[v]$。次回 Dijkstra のために incremental に更新。

計算量

Bellman-Ford: $O(VE)$（初回のみ）
Dijkstra 反復: $O(F \cdot E \log V)$
合計: $O(VE + F \cdot E \log V)$

よくあるミス

ミス	原因	正しい書き方
負辺で Dijkstra のみ使う	負辺は Dijkstra を壊す	Bellman-Ford → Johnson 変換
ポテンシャル更新忘れ	毎回 Bellman-Ford は遅い	`h[v] += dist[v]` incremental
$h[v]=\infty$ の頂点	残余ポテンシャルが NaN 化	到達不能頂点は `h=0` に補正
逆辺の `rev_index` 不整合	順・逆辺のペアが壊れる	`len(graph[v])`, `len(graph[u])-1` で正確
$F$ 流せない判定漏れ	途中で $t$ 不到達	`if dist[t] == INF: return -1`

Day 037-Q5 — 最小費用流（負辺対応 Johnson ポテンシャル + 繰り返し Dijkstra）

問題

制約