Day 109-Q3 — Cycle-Canceling Algorithm（負閉路除去法）

2026-08-01 赤色 Master / Phase 8+ ★★★★★★★★★ 最小費用流の減算的解法・Bellman-Ford系の負閉路検出

問題

頂点数 $N$、辺数 $M$ の有向グラフが与えられる。各辺には容量(cap)とコスト(cost)がある。

頂点 $S$ から頂点 $T$ へちょうど $F$ 単位の流量を流すときの最小総コストを求めよ。ただし、必ず Cycle-Canceling法（負閉路除去法） を用いて解くこと。

手順: (1) コストを無視して$S$-$T$間にちょうど$F$単位の実行可能流を1つ求める。(2) 残余グラフ上でコストの符号付き和が負になる閉路（負閉路）をBellman-Ford系のアルゴリズムで検出する。(3) 見つかった閉路のボトルネック容量ぶんだけ流量をキャンセルする。(4) 負閉路が見つからなくなるまで(2)(3)を繰り返す。

入力形式

N M S T F
u_1 v_1 cap_1 cost_1
...
u_M v_M cap_M cost_M

制約

$2 \le N \le 100$
$1 \le M \le 300$
$1 \le F \le 100$
$1 \le \text{cap}_i, \text{cost}_i \le 20$
$S$から$T$へ$F$単位以上流せることが保証される

入出力例

入力例1

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

出力例1

9

経路0→2→3はコスト2+1=3/単位で容量2、経路0→1→2→3もコスト1+1+1=3/単位。前者を2単位、後者を1単位流すと合計3単位・コスト3×2+3×1=9。これが最小。

概念図: 負閉路の検出とキャンセル

残余グラフ上の負コスト閉路をキャンセル u v w x cost +2 cost +1 cost -5 (逆辺) cost +1 閉路u→v→w→x→uのコスト和 = 2+1-5+1 = -1（負）→この方向にキャンセルすると総コストが減る

ヒント（段階的開示）

ヒント1: 方向性
最小費用流の標準解法「逐次最短路法（Successive Shortest Path）」は、流量を少しずつ増やしながら最短費用路に沿って流す加算的なアプローチである。Cycle-Canceling法はこれとは逆に、「先にコストを無視して適当な実行可能流を確保し、その後で改善できる部分を直していく」という減算的なアプローチを取る。
ヒント2: アプローチ
残余グラフのある閉路に沿って単位流量を追加すると、総コストの変化量はその閉路上の各辺のコストの符号付き和（順方向は+cost、逆方向は-cost）に等しい。この和が負であれば、その閉路方向に流量を流すことで総コストを削減できる。

負閉路の検出には、全頂点を始点距離0で初期化したBellman-Ford（SPFA）を用いる。通常のBellman-Fordは$N-1$回の緩和で収束するが、ある頂点が$N$回を超えて緩和され続ける場合、それは負閉路に巻き込まれていることを意味する。そこから親ポインタを$N$回遡ることで確実に閉路上の頂点にたどり着き、そこから親を辿り続けて閉路を復元できる。
ヒント3: 誘導（コード骨格） 
def find_negative_cycle(graph, n):
    dist = [0]*n            # 全頂点を距離0で初期化（負閉路検出の工夫）
    prevv, preve, cnt = [-1]*n, [-1]*n, [0]*n
    queue = deque(range(n))
    inqueue = [True]*n
    while queue:
        u = queue.popleft(); inqueue[u] = False
        for i, (v, cap, cost, rev) in enumerate(graph[u]):
            if cap > 0 and dist[u] + cost < dist[v]:
                dist[v] = dist[u] + cost
                prevv[v], preve[v] = u, i
                if not inqueue[v]:
                    queue.append(v); inqueue[v] = True
                    cnt[v] += 1
                    if cnt[v] > n:
                        # vはn回を超えて緩和された→負閉路に巻き込まれている
                        # prevvをn回遡ってから閉路を復元する
                        ...

模範解答 (Python)

import sys
from collections import deque

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    s = int(data[idx]); idx += 1
    t = int(data[idx]); idx += 1
    F = int(data[idx]); idx += 1

    graph = [[] for _ in range(n)]
    edge_ref = []

    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])
        edge_ref.append((u, len(graph[u]) - 1, cap))

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

    # Step 1: コストを無視してS-T間にちょうどF単位の実行可能流を求める
    flow = 0
    while flow < F:
        prevv = [-1] * n
        preve = [-1] * n
        visited = [False] * n
        visited[s] = True
        q = deque([s])
        while q:
            u = q.popleft()
            for i, e in enumerate(graph[u]):
                v, cap, cost, rev = e
                if cap > 0 and not visited[v]:
                    visited[v] = True
                    prevv[v] = u
                    preve[v] = i
                    q.append(v)
        d = F - flow
        v = t
        while v != s:
            d = min(d, graph[prevv[v]][preve[v]][1])
            v = prevv[v]
        v = t
        while v != s:
            e = graph[prevv[v]][preve[v]]
            e[1] -= d
            graph[v][e[3]][1] += d
            v = prevv[v]
        flow += d

    # Step 2: 負閉路が存在しなくなるまでキャンセルし続ける
    def find_negative_cycle():
        dist = [0] * n
        inqueue = [True] * n
        prevv = [-1] * n
        preve = [-1] * n
        cnt = [0] * n
        q = deque(range(n))
        while q:
            u = q.popleft()
            inqueue[u] = False
            for i, e in enumerate(graph[u]):
                v, cap, cost, rev = e
                if cap > 0 and dist[u] + cost < dist[v]:
                    dist[v] = dist[u] + cost
                    prevv[v] = u
                    preve[v] = i
                    if not inqueue[v]:
                        q.append(v)
                        inqueue[v] = True
                        cnt[v] += 1
                        if cnt[v] > n:
                            x = v
                            for _ in range(n):
                                x = prevv[x]
                            cycle = []
                            cur = x
                            while True:
                                cycle.append((prevv[cur], preve[cur]))
                                cur = prevv[cur]
                                if cur == x:
                                    break
                            cycle.reverse()
                            return cycle
        return None

    while True:
        cyc = find_negative_cycle()
        if cyc is None:
            break
        bottleneck = min(graph[u][ei][1] for u, ei in cyc)
        for u, ei in cyc:
            e = graph[u][ei]
            e[1] -= bottleneck
            graph[e[0]][e[3]][1] += bottleneck

    total_cost = 0
    for (u, ei, orig_cap) in edge_ref:
        v, cap_left, cost, rev = graph[u][ei]
        total_cost += (orig_cap - cap_left) * cost

    print(total_cost)

solve()
計算量: 実行可能流の構築$O(F\cdot M)$、負閉路の検出・キャンセルが1回あたり$O(NM)$。200回のランダムなグラフで逐次最短路法による参照実装と総コストを突き合わせるストレステストで一致を確認済み。

Step-by-Step 解説

1まずコストを無視してF単位の実行可能流を作る
単純なBFS augmenting pathを使い、コストは一切見ずに$S$から$T$へちょうど$F$単位流す。
2残余グラフでの負閉路検出にBellman-Ford（SPFA）を使う
残余グラフには負の辺重み（逆辺）が混在するためダイクストラ法は使えない。全頂点の距離を0で初期化し、緩和回数が$N$回を超えたら負閉路に巻き込まれていると判定する。
3親ポインタをN回遡ってから閉路を復元する
緩和回数が超過した頂点から直接復元を始めると「しっぽ」を含む可能性がある。$N$回遡ることで確実に閉路内部の頂点にたどり着く。
4閉路のボトルネック容量ぶんだけキャンセルする
閉路上の残り容量が最小の辺がボトルネック。そのぶんだけ閉路方向に流量を追加すると、閉路の総コストが負なので全体のコストが必ず減少する。
5負閉路がなくなったら最適性が保証される
線形計画法の双対性から、「残余グラフに負閉路が存在しない」ことと「現在の流が最小費用流である」ことは同値である（負閉路最適性条件）。

よくあるミス

ミス原因正しい書き方
逆辺のコストの符号を忘れる順方向のコストをそのまま逆辺にコピーしてしまう逆辺のコストは必ず-costにする
Step 1の実行可能流探索でコストを考慮してしまう最短路探索のつもりでコスト付きBFSを書いてしまうStep 1はコストを完全に無視した単純なBFS augmenting pathにする
負閉路の復元時にN回親を遡る処理を省略する緩和回数超過を検出した頂点からすぐ閉路復元を始めてしまう必ずprevvを$N$回遡ってから、その頂点を起点に閉路を復元する
キューに同じ頂点を重複して入れてしまいSPFAが悪化するinqueueフラグの更新漏れキュー追加時にinqueue[v]=True、取り出し時にinqueue[u]=Falseを対で管理する

次のステップ

  • 発展: 負閉路検出をBellman-Fordの代わりにJohnson法（ポテンシャル付きダイクストラ）に置き換え、実行時間を比較する
  • 発展: 「最も負なコストの閉路から優先的にキャンセルする」戦略（Minimum Mean Cycle-Canceling）に変更する
  • 発展: 逐次最短路法で同じ問題を解き、両者の反復回数・実行時間を比較する

自己評価

自分の回答

気づき・メモ