Day 150-Q2 | Cycle Canceling法

問題

$N$頂点・$M$辺の有向グラフが与えられる。頂点$0$が始点、頂点$N-1$が終点。各辺には容量とコスト（1単位の流量を流すのにかかる費用）が定められている。以下の2段階の手順を厳密に実行し、最終的な総コストを求めよ。

Step A（コストを無視した最大流の構築）

残余グラフ上で、頂点0からDFS（スタック使用、同じ頂点から出る辺は入力順に処理）で$t$への増加路を見つけたらボトルネック容量だけ流す。増加路が無くなるまで繰り返す。

Step B（Cycle Canceling法）

残余グラフにBellman-Ford法（全頂点dist=0開始、全辺を入力順にチェックする緩和を$N$回）で負閉路を検出する。$N$回目の緩和で更新された頂点からparentを$N$回遡って閉路上の頂点を特定し、閉路を復元。ボトルネック残余容量だけキャンセルする。負閉路が消えるまで繰り返す。

入力形式

N M
u_1 v_1 cap_1 cost_1
:
u_M v_M cap_M cost_M

制約

$2 \le N \le 20$

$1 \le M \le 40$

容量は $1$〜$20$

コストは $1$〜$10$（入力に負コスト辺なし）

入出力例

入力例1

出力例1

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

ヒント（段階的開示）

ヒント1（方向性）

Step Aで求めた最大流はコストを一切考慮していない。しかし最大流量そのものは、コストを最小化した後も変わらない。コスト最小化は流量を保ったまま辺の流し方だけを最適化する。

ヒント2（アプローチ）

残余グラフに合計コストが負になる閉路が存在するなら、その閉路に沿って流量を回すだけで総コストを下げられる。どの閉路も合計コストが0以上なら、これ以上下げる操作が無い＝最適（負閉路最適性定理）。これが停止条件になる。

ヒント3（誘導）

def bellman_ford_negcycle(N, edges, residual_cap):
    dist = [0]*N
    parent_edge = [-1]*N
    x = -1
    for _ in range(N):
        x = -1
        for idx, e in enumerate(edges):
            if residual_cap(idx) > 0 and dist[e.u] + e.cost < dist[e.v]:
                dist[e.v] = dist[e.u] + e.cost
                parent_edge[e.v] = idx
                x = e.v
    if x == -1:
        return None
    for _ in range(N):
        x = edges[parent_edge[x]].u
    # x を N 回遡ることで確実に閉路上の頂点に到達する

模範解答 (Python)

import sys


class Edge:
    __slots__ = ("u", "v", "cap", "cost", "flow")

    def __init__(self, u, v, cap, cost):
        self.u = u
        self.v = v
        self.cap = cap
        self.cost = cost
        self.flow = 0


def main():
    data = sys.stdin.read().split()
    ptr = 0
    n = int(data[ptr]); ptr += 1
    m = int(data[ptr]); ptr += 1

    edges = []
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u = int(data[ptr]); v = int(data[ptr + 1])
        cap = int(data[ptr + 2]); cost = int(data[ptr + 3])
        ptr += 4
        e = Edge(u, v, cap, cost)
        r = Edge(v, u, 0, -cost)
        edges.append(e); edges.append(r)
        graph[u].append(len(edges) - 2)
        graph[v].append(len(edges) - 1)

    def rescap(idx):
        return edges[idx].cap - edges[idx].flow

    def send(idx, amt):
        edges[idx].flow += amt
        edges[idx ^ 1].flow -= amt

    def find_augmenting_path():
        parent_edge = [-1] * n
        visited = [False] * n
        stack = [0]
        visited[0] = True
        while stack:
            u = stack.pop()
            if u == n - 1:
                break
            for idx in graph[u]:
                v = edges[idx].v
                if not visited[v] and rescap(idx) > 0:
                    visited[v] = True
                    parent_edge[v] = idx
                    stack.append(v)
        if not visited[n - 1]:
            return None
        path = []
        v = n - 1
        while v != 0:
            idx = parent_edge[v]
            path.append(idx)
            v = edges[idx].u
        path.reverse()
        return path

    while True:
        path = find_augmenting_path()
        if path is None:
            break
        bottleneck = min(rescap(idx) for idx in path)
        for idx in path:
            send(idx, bottleneck)

    def find_negative_cycle():
        dist = [0] * n
        parent_edge = [-1] * n
        x = -1
        for _ in range(n):
            x = -1
            for idx, e in enumerate(edges):
                if rescap(idx) > 0 and dist[e.u] + e.cost < dist[e.v]:
                    dist[e.v] = dist[e.u] + e.cost
                    parent_edge[e.v] = idx
                    x = e.v
        if x == -1:
            return None
        for _ in range(n):
            x = edges[parent_edge[x]].u
        cycle = []
        v = x
        while True:
            idx = parent_edge[v]
            cycle.append(idx)
            v = edges[idx].u
            if v == x:
                break
        cycle.reverse()
        return cycle

    while True:
        cyc = find_negative_cycle()
        if cyc is None:
            break
        bottleneck = min(rescap(idx) for idx in cyc)
        for idx in cyc:
            send(idx, bottleneck)

    total_cost = sum(e.flow * e.cost for e in edges if e.flow > 0)
    print(total_cost)


main()

Step-by-Step 解説

1コスト無視の最大流（Step A）
DFS（スタック・入力辺順）で流量4の最大流を構築。0→1:2, 0→2:2, 1→2:1, 1→3:1, 2→3:3、総コスト2+6+1+3+3=15。

2残余グラフに負閉路を探す
1→2(cost1,残余1)・2→0(逆辺,cost-3)・0→1(残余1,cost1)の3辺で合計コスト1-3+1=-1の負閉路。

3閉路を1単位キャンセル
ボトルネックは1。押し流すと総コストは15+(-1)*1=14に減少。

4負閉路が消えるまで繰り返す
再度Bellman-Fordを実行すると負閉路は見つからず(x==-1)終了。最終コスト14、流量4はStep Aから不変。

よくあるミス

ミス	原因	正しい書き方
逆辺のコストを正のままにする	符号反転を忘れる	逆辺のコストは必ず`-cost`にする
Bellman-Fordの緩和を`N-1`回で止める	通常の最短路検出の回数を流用	負閉路検出には`N`回目の更新有無を見る
更新頂点をそのまま閉路の一部として使う	検出ロジックの誤解	`parent_edge`をN回遡ってから閉路復元を始める
ボトルネック計算を怠る	残余容量チェック漏れ	閉路上全辺の残余容量の最小値を使う
Step Aを飛ばしてStep Bだけ実行	「最初から負閉路を探せばよい」と誤解	実行可能な流が無いと負閉路検出の前提が崩れるため、必ずStep Aを先に行う

次のステップ

発展: Bellman-Fordベースの検出は毎回$O(NM)$かかるため非効率。SSP法（ポテンシャル付きダイクストラ）に切り替えると全体で$O(M\log N)$回のダイクストラに削減できる。
次回予告: 分枝限定法（Branch and Bound・0/1ナップサック問題）

自己評価

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

Day 150-Q2 — Cycle Canceling法（最小費用流の負閉路除去法）

問題