Day 025-Q3 — フロー分解定理 + 最小費用循環流

問題

$N$ 頂点 $M$ 辺の有向グラフ。各辺に容量 $c$、コスト $d$、下限流量 $l$。最小費用循環流とそのパス・サイクル分解を求めよ。

制約

入出力例

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

Minimum cost: 12
Flow decomposition:
Cycle: 1 -> 2 -> 3 -> 1, flow=2, cost=12

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from collections import deque, defaultdict
input = sys.stdin.readline
INF = float('inf')

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

    def add_edge(self, u, v, cap, cost):
        fwd = len(self.graph[u])
        bwd = len(self.graph[v])
        self.graph[u].append([v, cap, cost, bwd])
        self.graph[v].append([u, 0, -cost, fwd])
        return fwd

    def min_cost_flow(self, s, t, max_flow=INF):
        total_flow = 0
        total_cost = 0
        while True:
            dist = [INF] * self.n
            in_queue = [False] * self.n
            prev_v = [-1] * self.n
            prev_e = [-1] * self.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(self.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 = max_flow - total_flow
            v = t
            while v != s:
                d = min(d, self.graph[prev_v[v]][prev_e[v]][1])
                v = prev_v[v]
            if d == 0: break
            v = t
            while v != s:
                self.graph[prev_v[v]][prev_e[v]][1] -= d
                rev = self.graph[prev_v[v]][prev_e[v]][3]
                self.graph[v][rev][1] += d
                v = prev_v[v]
            total_flow += d
            total_cost += d * dist[t]
            if total_flow >= max_flow: break
        return total_flow, total_cost

def main():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, c, d, l = map(int, input().split())
        edges.append((u - 1, v - 1, c, d, l))
    S, T = N, N + 1
    mcf = MinCostFlow(N + 2)
    b = [0] * N
    edge_indices = []
    for idx, (u, v, c, d, l) in enumerate(edges):
        ei = mcf.add_edge(u, v, c - l, d)
        edge_indices.append((u, ei))
        b[v] += l; b[u] -= l
    required_flow = 0
    for v in range(N):
        if b[v] > 0:
            mcf.add_edge(S, v, b[v], 0); required_flow += b[v]
        elif b[v] < 0:
            mcf.add_edge(v, T, -b[v], 0)
    flow, cost = mcf.min_cost_flow(S, T, required_flow)
    if flow < required_flow:
        print("No feasible circulation exists."); return
    actual_flow = []
    base_cost = sum(l * d for _, _, _, d, l in edges)
    for idx, (u, v, c, d, l) in enumerate(edges):
        eu, ei = edge_indices[idx]
        used_cap = (c - l) - mcf.graph[eu][ei][1]
        actual_flow.append(l + used_cap)
    total_cost = cost + base_cost
    print(f"Minimum cost: {total_cost}")

    flow_graph = defaultdict(lambda: defaultdict(int))
    for idx, (u, v, c, d, l) in enumerate(edges):
        if actual_flow[idx] > 0:
            flow_graph[u][v] += actual_flow[idx]
    decomposed = []

    def find_cycle():
        for start in range(N):
            if not any(flow_graph[start].values()): continue
            path = [start]; visited = {start: 0}; v = start
            while True:
                moved = False
                for nxt, f in list(flow_graph[v].items()):
                    if f > 0:
                        if nxt in visited:
                            cs = visited[nxt]
                            cycle = path[cs:]
                            cf = min(flow_graph[cycle[i]][cycle[(i+1) % len(cycle)]] for i in range(len(cycle)))
                            for i in range(len(cycle)):
                                flow_graph[cycle[i]][cycle[(i+1) % len(cycle)]] -= cf
                            return cycle, cf
                        path.append(nxt); visited[nxt] = len(path) - 1; v = nxt; moved = True; break
                if not moved: break
        return None, 0

    for _ in range(M * 2):
        cycle, flow_val = find_cycle()
        if cycle is None: break
        if flow_val > 0:
            cycle_cost = 0
            for i in range(len(cycle)):
                u, v = cycle[i], cycle[(i+1) % len(cycle)]
                for idx2, (eu, ev, ec, ed, el) in enumerate(edges):
                    if eu == u and ev == v:
                        cycle_cost += ed * flow_val; break
            decomposed.append(("Cycle", cycle + [cycle[0]], flow_val, cycle_cost))

    print("Flow decomposition:")
    if not decomposed:
        print("(no flow)")
    else:
        for kind, path, f, c in decomposed:
            path_str = " -> ".join(str(v + 1) for v in path)
            print(f"{kind}: {path_str}, flow={f}, cost={c}")

main()

Step-by-Step 解説

よくあるミス

次のステップ

• 下限付き最大流
• プロジェクトスケジューリング (CPM + 下限)

自己評価

自分の回答

気づき・メモ