Day 011-Q5 — 最小費用流

2026-04-24 橙色 / Phase 7 ★★★★★★★ Min Cost Flow

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺は容量 $cap$ とコスト $cost$ を持つ。ソース $s$ からシンク $t$ へ 流量 $F$ を流すとき の最小費用を求めよ。

流量 $F$ を流せない場合は -1 を出力せよ。

入力形式

N M s t F
u_1 v_1 cap_1 cost_1
...（M行）

制約

$2 \le N \le 500$
$1 \le M \le 5000$
$0 \le cap_i \le 10^9$
$-10^4 \le cost_i \le 10^4$（負コストあり）
$1 \le F \le 10^9$

入出力例

入力例 1

4 5 0 3 2
0 1 2 2
0 2 1 6
1 2 1 1
1 3 1 3
2 3 2 2

出力例 1

13

ヒント (段階的開示)

ヒント1: 方向性
最小費用流（Minimum Cost Flow）は「費用の最小な増加路を繰り返し選んで流量 $F$ まで増やす」アルゴリズム。増加路の選択に ポテンシャル付き Dijkstra（SPFA も可） を使う。
ヒント2: アプローチ
  1. 最短路（最小費用路）を Bellman-Ford または SPFA で見つける
  2. その路に沿ってボトルネック容量を流す
  3. 逆辺（残余グラフ）を更新する
  4. 流量が $F$ になるまで繰り返す
ヒント3: 誘導 
# 辺: [to, cap, cost, rev_index]
graph = [[] for _ in range(N)]

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])

# SPFA で最短路を探す
def spfa(s, t):
    dist = [INF] * N
    in_queue = [False] * N
    from collections import deque
    q = deque([s])
    dist[s] = 0
    ...

模範解答 (Python)

import sys
from collections import deque
input = sys.stdin.readline
INF = float('inf')

def main():
    N, M, s, t, F = map(int, input().split())
    graph = [[] for _ in range(N)]

    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, v, cap, cost = map(int, input().split())
        add_edge(u, v, cap, cost)

    total_flow = 0
    total_cost = 0

    while total_flow < F:
        # SPFA（ベルマンフォードのキュー版）で最短路
        dist = [INF] * N
        in_queue = [False] * N
        prev_v = [-1] * N
        prev_e = [-1] * N
        dist[s] = 0
        q = deque([s])
        in_queue[s] = True

        while q:
            v = q.popleft()
            in_queue[v] = False
            for i, (to, cap, cost, _) in enumerate(graph[v]):
                if cap > 0 and dist[v] + cost < dist[to]:
                    dist[to] = dist[v] + cost
                    prev_v[to] = v
                    prev_e[to] = i
                    if not in_queue[to]:
                        q.append(to)
                        in_queue[to] = True

        if dist[t] == INF:
            break  # これ以上流せない

        # ボトルネック容量を計算
        d = F - total_flow
        v = t
        while v != s:
            d = min(d, graph[prev_v[v]][prev_e[v]][1])
            v = prev_v[v]

        # 流す
        v = t
        while v != s:
            e = graph[prev_v[v]][prev_e[v]]
            e[1] -= d
            graph[v][e[3]][1] += d
            v = prev_v[v]

        total_flow += d
        total_cost += d * dist[t]

    if total_flow < F:
        print(-1)
    else:
        print(total_cost)

main()

Step-by-Step 解説

1残余グラフの構築
各辺 $(u \to v, cap, cost)$ に対して 逆辺 $(v \to u, 0, -cost)$ を追加する。容量0の逆辺を使うことで「流しを取り消す」操作を表現できる。
2SPFA（Shortest Path Faster Algorithm）
Bellman-Ford のキュー版で、最短費用路（最小コスト増加路）を見つける。負コスト辺があるため Dijkstra 素直には使えない（ポテンシャル法を使えば可能）。
3ボトルネック容量の計算
最短路上を逆向きにたどり、最小容量（ボトルネック）を求める。$F - \text{total\_flow}$ との min を取って流量を確定。
4辺の更新
流した量 $d$ だけ:
  • 正辺: cap -= d
  • 逆辺: cap += d
5繰り返しと終了条件
total_flow >= F になるか、増加路がなくなれば終了。増加路なしで total_flow < F なら -1。

よくあるミス

ミス原因正しい書き方
逆辺のコストを 0 にする+cost を使わないと差分が壊れる逆辺のコストは -cost
ボトルネック計算で F を考慮しない流しすぎるmin(d, F - total_flow)
SPFA のキューに重複追加in_queue フラグ管理ミスin_queue[to] が False のときのみ追加
負コスト辺を Dijkstra で処理負辺では正確でないSPFA か Johnson 法（ポテンシャル付きDijkstra）

次のステップ

  • 発展: ポテンシャル法（Johnson's algorithm）でDijkstraを使い高速化
  • 応用: 割り当て問題（Hungarian法）を最小費用流で解く
  • 実装: AtCoder Library の mcf_graph を使った実装

自己評価

自分の回答

気づき・メモ