Day 013-Q1 — 線形計画・半正定値計画

問題

N 頂点 M 辺の有向グラフ。各辺 i は容量 $c_i$、下限流量 $l_i$、コスト $w_i$。各辺に流量 $f_i$（$l_i \le f_i \le c_i$）を割り当て、全頂点でフロー保存則を満たし、コスト $\sum w_i f_i$ を最小化（ソース・シンクなし、循環流）。

制約

入出力例

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

5

ヒント (段階的開示)

for u, v, l, c, w in edges:
    demand[v] += l
    demand[u] -= l
# demand > 0 の頂点へ S から、 < 0 から T へ辺追加

模範解答 (Python)

📋 コピーimport sys
from collections import defaultdict, deque
input = sys.stdin.readline

class MCMF:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
    def add_edge(self, u, v, cap, cost):
        self.graph[u].append([v, cap, cost, len(self.graph[v])])
        self.graph[v].append([u, 0, -cost, len(self.graph[u]) - 1])
    def min_cost_flow(self, s, t, max_flow):
        INF = float('inf')
        flow = cost = 0
        while flow < max_flow:
            dist = [INF] * self.n
            dist[s] = 0
            in_queue = [False] * self.n
            prev_v = [-1] * self.n
            prev_e = [-1] * self.n
            q = deque([s]); in_queue[s] = True
            while q:
                v = q.popleft(); in_queue[v] = False
                for i, (nv, cap, c, _) in enumerate(self.graph[v]):
                    if cap > 0 and dist[v] + c < dist[nv]:
                        dist[nv] = dist[v] + c
                        prev_v[nv] = v; prev_e[nv] = i
                        if not in_queue[nv]:
                            q.append(nv); in_queue[nv] = True
            if dist[t] == INF:
                break
            d = max_flow - flow
            v = t
            while v != s:
                d = min(d, self.graph[prev_v[v]][prev_e[v]][1])
                v = prev_v[v]
            v = t
            while v != s:
                self.graph[prev_v[v]][prev_e[v]][1] -= d
                self.graph[v][self.graph[prev_v[v]][prev_e[v]][3]][1] += d
                v = prev_v[v]
            flow += d
            cost += d * dist[t]
        return flow, cost

def solve():
    N, M = map(int, input().split())
    edges = []
    for _ in range(M):
        u, v, l, c, w = map(int, input().split())
        edges.append((u-1, v-1, l, c, w))
    S = N; T = N + 1
    mcmf = MCMF(N + 2)
    demand = [0] * N
    base_cost = 0
    for u, v, l, c, w in edges:
        mcmf.add_edge(u, v, c - l, w)
        demand[v] += l
        demand[u] -= l
        base_cost += w * l
    total_supply = 0
    for i in range(N):
        if demand[i] > 0:
            mcmf.add_edge(S, i, demand[i], 0)
            total_supply += demand[i]
        elif demand[i] < 0:
            mcmf.add_edge(i, T, -demand[i], 0)
    flow, cost = mcmf.min_cost_flow(S, T, total_supply)
    print(base_cost + cost)

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• ソース・シンクがある場合の下限付き最小費用流（S→T 辺補完）

自己評価

自分の回答

気づき・メモ