Day 047-Q4 | 下限付き最小費用循環流（変数変換 + ポテンシャル法 + MCMF）

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる。各辺 $e_i$ は容量 $\text{cap}_i$、下限流量 $\text{lo}_i \ge 0$、コスト $w_i$（負の値あり）を持つ。

下限付き最小費用循環流問題を解け：各辺の流量 $f_i$ が $\text{lo}_i \le f_i \le \text{cap}_i$ を満たす循環流（各頂点で流量保存）を見つけ、$\sum_i w_i f_i$ を最小化せよ。実行可能循環流が存在しない場合は -1 を出力せよ。

制約

$2 \le N \le 300$

$1 \le M \le 3000$

$0 \le \text{lo}_i \le \text{cap}_i \le 10^4$

$-10^4 \le w_i \le 10^4$

時間制限: 3秒

入出力例

入力例 1

出力例 1

概念図: 下限付き循環流の変換手順

ヒント（段階的開示）

ヒント1: 方向性

下限付き循環流問題は、下限流量の強制と負辺の処理の2段階で考えます。まず下限を「差し引いて」通常の最小費用最大流問題に帰着させます。負コスト辺は Johnson のポテンシャル法（初期 Bellman-Ford）で非負化します。

ヒント2: アプローチ

下限変換: 辺 $(u,v)$ の下限 $\text{lo}$ を処理するため、$b[u] -= \text{lo}$, $b[v] += \text{lo}$（超過量）。辺の容量を $\text{cap} - \text{lo}$ に変換。$\text{fixed\_cost} += \text{lo} \times w$。
補助辺の追加: 超過源 $S$、不足源 $T$ を追加。$b[v] > 0$ なら $S \to v$（容量 $b[v]$、コスト 0）、$b[v] < 0$ なら $v \to T$（容量 $-b[v]$、コスト 0）。
最小費用最大流 を $(S, T)$ 間で解き、$S$ から出る全辺が飽和すれば実行可能。
負辺の非負化: Bellman-Ford でポテンシャルを初期化し、以降 Dijkstra（Johnson 法）。

ヒント3: MCMF クラスの骨格

class MCMF:
    def add_edge(self, u, v, cap, cost):
        self.g[u].append([v, cap, cost, len(self.g[v])])
        self.g[v].append([u, 0, -cost, len(self.g[u]) - 1])

    def min_cost_flow(self, s, t, f=None):
        # Bellman-Ford でポテンシャルを初期化（負辺対応）
        h = Bellman-Ford(s)
        # Dijkstra (ポテンシャル法) で増加路を繰り返し発見
        while True:
            dist = Dijkstra(s, h)
            if dist[t] == INF: break
            h[i] += dist[i]  # ポテンシャル更新
            # 最小容量を流す
            ...

模範解答 (Python)

import sys
from heapq import heappush, heappop
input = sys.stdin.readline

class MCMF:
    INF = float('inf')

    def __init__(self, n):
        self.n = n
        self.g = [[] for _ in range(n)]

    def add_edge(self, u, v, cap, cost):
        self.g[u].append([v, cap, cost, len(self.g[v])])
        self.g[v].append([u, 0, -cost, len(self.g[u]) - 1])

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

        total_flow = 0
        total_cost = 0

        while True:
            dist = [INF] * n
            dist[s] = 0
            prev = [-1] * n
            prev_e = [-1] * n
            pq = [(0, s)]

            while pq:
                d, u = heappop(pq)
                if d > dist[u]:
                    continue
                for i, (v, cap, cost, _) in enumerate(g[u]):
                    if cap > 0:
                        nd = dist[u] + cost + h[u] - h[v]
                        if nd < dist[v]:
                            dist[v] = nd
                            prev[v] = u
                            prev_e[v] = i
                            heappush(pq, (nd, v))

            if dist[t] == INF:
                break

            for i in range(n):
                if dist[i] < INF:
                    h[i] += dist[i]

            d = INF
            v = t
            while v != s:
                u = prev[v]
                e = prev_e[v]
                d = min(d, g[u][e][1])
                v = u

            v = t
            while v != s:
                u = prev[v]
                e = prev_e[v]
                g[u][e][1] -= d
                g[v][g[u][e][3]][1] += d
                v = u

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

        return total_flow, total_cost


def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, lo, cap, w = map(int, input().split())
        edges.append((u-1, v-1, lo, cap, w))

    S, T = N, N + 1
    mcmf = MCMF(N + 2)

    b = [0] * N
    fixed_cost = 0

    for u, v, lo, cap, w in edges:
        b[u] -= lo
        b[v] += lo
        fixed_cost += lo * w
        mcmf.add_edge(u, v, cap - lo, w)

    need = 0
    for v in range(N):
        if b[v] > 0:
            mcmf.add_edge(S, v, b[v], 0)
            need += b[v]
        elif b[v] < 0:
            mcmf.add_edge(v, T, -b[v], 0)

    flow, cost = mcmf.min_cost_flow(S, T)

    if flow < need:
        print(-1)
    else:
        print(cost + fixed_cost)

main()

Step-by-Step 解説

1下限付き循環流の変換
辺 $(u,v)$ に下限 $\text{lo}$ があるとき、まず $\text{lo}$ 単位を強制的に流す。この強制流は頂点の「超過量」$b[v]$ を変化させる：$b[u] -= \text{lo}$, $b[v] += \text{lo}$。辺の容量は $\text{cap} - \text{lo}$ に減らす。

2補助頂点でバランスを取る
$b[v] > 0$（超過）の頂点には超過源 $S$ から辺を張り（容量 $b[v]$、コスト 0）、$b[v] < 0$（不足）の頂点には不足源 $T$ への辺を張る。$(S,T)$ 間の最大流が need に等しければ実行可能。

3負コスト辺の処理（Johnson ポテンシャル法）
Bellman-Ford で最短路ポテンシャル $h[]$ を初期化することで、全辺のリダクションコスト $\text{cost} + h[u] - h[v]$ が非負になる。以降は Dijkstra で $O((V+E) \log V)$ で最短路を求められる。

4最小費用最大流のメインループ
各反復で Dijkstra で最短増加路を発見 → 流す。ポテンシャルを更新（$h[i] += dist[i]$）。実際コストは $d \times h[t]$（ポテンシャルで補正済み距離の累積）。

5fixed_cost の加算
下限変換時に強制流のコスト $\text{fixed\_cost} = \sum \text{lo}_i \times w_i$ を別途積算しておく。最終答えは $\text{cost} + \text{fixed\_cost}$。

計算量

Bellman-Ford 初期化: $O(V \cdot E)$
MCMF メインループ（各反復）: $O((V+E) \log V)$
全体: $O(F \cdot (V+E) \log V)$（$F$ = 最大流量）
本問: $N \le 300, M \le 3000, \text{cap} \le 10^4$ → 実用的に十分

よくあるミス

ミス	原因	正しい書き方
Bellman-Ford のポテンシャル初期化を省略	負辺で Dijkstra が誤った結果を返す	必ず Bellman-Ford で初期ポテンシャルを計算
fixed_cost を忘れる	強制流のコストを加算しない	`fixed_cost += lo * w` を変換時に積算
need が最大流に一致するか確認しない	実行不可能な場合に誤った答えを出力	`if flow < need: print(-1)`
リダクションコストが負になる	ポテンシャル更新のタイミングミス	増加路を流した後に `h[i] += dist[i]`

次のステップ

発展問題: 下限付き最小費用最大流（特定の $(s,t)$ 間で最大流を流しつつ各辺の下限を満たす）
関連: Day037 Q5（最小費用流負辺対応 Johnson ポテンシャル）の復習
応用: サプライチェーン最適化（倉庫間の在庫移動コスト最小化）

自己評価

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