Day 107-Q5 | 凸コストMin-Cost-Flow（単位容量辺への分解）

問題

$N$頂点$M$辺の有向グラフが与えられる。各辺$i$（$u_i\to v_i$、容量$c_i$）は、そこに流す量$f$（$0\le f\le c_i$）に対して凸コスト関数 $C_i(f)=A_if^2+B_if$（$A_i\ge0$）のコストがかかる。

頂点$S$から頂点$T$へちょうど$F$の流量を流すとき、全辺のコストの総和を最小化せよ。実現不可能なら-1を出力せよ。

入力形式

N M S T F
u_1 v_1 c_1 A_1 B_1
...
u_M v_M c_M A_M B_M

制約

$2 \le N \le 100$

$1 \le M \le 200$

$1 \le c_i \le 1000$

$0 \le A_i \le 10,\ 0 \le B_i \le 1000$

入出力例

入力例1

出力例1

経路1→2→4に2、経路1→3→4に3流すと合計コストが最小の35になる（各経路の凸コストは辺ごとの限界費用の累積で計算される）。

概念図: 凸コスト辺を単位容量辺の等差数列に分解

ヒント（段階的開示）

ヒント1: 方向性

最小費用流（MCMF）の標準的な定式化は「辺1本あたりのコストが流量に比例する（線形コスト）」ケースを扱う。しかし本問のように「流す量が増えるほど単位あたりのコストが上がっていく」凸コストの場合、単純に「容量c、コスト(平均コスト)」のような1本の辺として扱うと凸性を表現できず、最適解を誤る。

ヒント2: アプローチ

凸関数$C(f)$の重要な性質は「限界費用（1単位追加するごとの増分コスト）が単調非減少」であること。$C_i(f)=A_if^2+B_if$の場合、$i$番目の単位を流すことによる限界費用は$C(i)-C(i-1)=A(2i-1)+B$であり、$A\ge0$ならこれは$i$について単調非減少になる。このことから、容量$c$の凸コスト辺を「容量1・コスト$A(2i-1)+B$の辺を$c$本並列に並べたもの」（$i=1,\dots,c$）として分解できる。標準的な最小費用流（successive shortest augmenting path、SSP）は「常にその時点で最も安い増加路から使っていく」ため、限界費用が小さい（＝番号が若い）並列辺から自動的に使われていく。限界費用が単調非減少であることが、SSPが単位を正しい順序で使うことを保証し、結果として真に最適な凸コスト割当が得られる。

ヒント3: 誘導（コード骨格）

# 1本の凸コスト辺 (u, v, cap, A, B) を、容量1の辺cap本に分解する
for i in range(1, cap + 1):
    marginal_cost = A * (2 * i - 1) + B   # i番目の1単位を流す限界費用
    add_edge(u, v, 1, marginal_cost)

# あとは通常の最小費用流（SSP + ポテンシャル法によるDijkstra高速化）で
# SからTへちょうどF流したときの最小コストを求めるだけでよい

模範解答 (Python)

import sys, heapq

INF = float('inf')

def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    S = int(data[idx]) - 1; idx += 1
    T = int(data[idx]) - 1; idx += 1
    F = int(data[idx]); idx += 1

    graph = [[] for _ in range(N)]
    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]) - 1; idx += 1
        v = int(data[idx]) - 1; idx += 1
        c = int(data[idx]); idx += 1
        A = int(data[idx]); idx += 1
        B = int(data[idx]); idx += 1
        # i番目(i=1..c)の1単位を流す限界費用: A*(2i-1)+B
        for i in range(1, c + 1):
            add_edge(u, v, 1, A * (2 * i - 1) + B)

    potential = [0] * N
    dist = [INF] * N
    dist[S] = 0
    for _ in range(N - 1):
        updated = False
        for u in range(N):
            if dist[u] == INF:
                continue
            for eid in graph[u]:
                if cap[eid] > 0 and dist[u] + cost[eid] < dist[to[eid]]:
                    dist[to[eid]] = dist[u] + cost[eid]
                    updated = True
        if not updated:
            break
    for v in range(N):
        if dist[v] < INF:
            potential[v] = dist[v]

    total_flow = 0
    total_cost = 0
    while total_flow < F:
        dist = [INF] * N
        dist[S] = 0
        prevedge = [-1] * N
        visited = [False] * N
        pq = [(0, S)]
        while pq:
            d, u = heapq.heappop(pq)
            if visited[u]:
                continue
            visited[u] = True
            for eid in graph[u]:
                v = to[eid]
                if cap[eid] <= 0 or visited[v]:
                    continue
                nd = d + cost[eid] + potential[u] - potential[v]
                if nd < dist[v]:
                    dist[v] = nd
                    prevedge[v] = eid
                    heapq.heappush(pq, (nd, v))
        if dist[T] == INF:
            break
        for v in range(N):
            if dist[v] < INF:
                potential[v] += dist[v]
        d = F - total_flow
        v = T
        while v != S:
            eid = prevedge[v]
            d = min(d, cap[eid])
            v = to[eid ^ 1]
        v = T
        while v != S:
            eid = prevedge[v]
            cap[eid] -= d
            cap[eid ^ 1] += d
            v = to[eid ^ 1]
        total_flow += d
        total_cost += d * potential[T]

    print(total_cost if total_flow == F else -1)


solve()

計算量: 分解後の辺数 $O(\sum c_i)$、SSP全体で $O(F \cdot E\log V)$ 程度。ランダム400ケースでbrute-force整数フロー全列挙と一致することを確認済み。

Step-by-Step 解説

1凸コストを限界費用の等差数列に分解
$C(f)=Af^2+Bf$のi番目の単位の限界費用$C(i)-C(i-1)=A(2i-1)+B$は初項$A+B$、公差$2A$の等差数列。$A\ge0$ならこの数列は単調非減少。

2分解後は通常の最小費用流としてSSPを適用
SSPは残余グラフ上で常に最も安い増加路を選び続けるため、同じ元の辺から分解された並列辺のうち限界費用が小さいものから優先的に使われる。これは凸関数の限界費用が単調非減少であることと整合し、最適な凸コスト割当が実現される。

3ポテンシャル法でDijkstraを使い高速化
分解後のグラフには逆辺（コスト負）が登場するため素朴なDijkstraは使えない。最初に一度だけBellman-Fordでポテンシャルを求め、以降はreduced costで非負を保ちながらDijkstraを毎回安全に適用する（Johnsonの手法）。

4目標流量Fに届かない場合は-1
増加路が見つからなくなった時点で流量がFに届いていなければ、その時点でのグラフの最大流量がF未満ということなので-1を出力する。

よくあるミス

ミス	原因	正しい書き方
凸コスト辺の容量が大きいと分解後の辺数が爆発する	容量cをそのままc本に展開すると大容量で非現実的になる	本問の制約(c≤1000)では問題ないが、大容量ならバイナリ分解や専用アルゴリズムを検討する
A=0のとき等差数列の公差が0になることを見落として単調性を疑う	全ての単位が同じ限界費用になるだけ	単調「非減少」であればSSPの正当性は保たれるので問題ない
ポテンシャル更新を忘れて2回目以降のDijkstraで負のreduced costが発生する	初回のBellman-Fordだけで満足してしまう	増加路を見つけるたびに必ずポテンシャルを更新してから次のDijkstraに進む
逆辺の容量・コストの初期化を忘れる	順辺だけ追加するとフローの取り消し（キャンセル）ができない	add_edgeで必ず順辺・逆辺のペアを同時に追加する

次のステップ

発展: 上に凸（concave）なコスト関数の場合を考える（この場合はSSPの単純な分解では最適性が保証されず、より高度な手法が必要）
発展: 頂点にも容量制約・凸コストがある場合（頂点分割によるグラフ変換と組み合わせる）
次回予告: Master Level ローテーション継続（新規テーマは次回セッションで選定）

自己評価

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

Day 107-Q5 — 凸コストMin-Cost-Flow（単位容量辺への分解）

問題