Day 173-Q4 — 2026-10-09 | 費用スケーリングの最小費用 b-フロー（ε-最適性と push/relabel）

📋 コピーimport sys
from collections import deque


def min_cost_b_flow(n, edges, b, alpha=8):
    # edges: (u, v, 容量, 費用)。b[v] = 供給（正）/ 需要（負）。実行可能が前提
    m = len(edges)
    to = [0] * (2 * m)
    cap = [0] * (2 * m)
    cost = [0] * (2 * m)
    frm = [0] * (2 * m)
    g = [[] for _ in range(n)]
    for i, (u, v, c, w) in enumerate(edges):
        to[2 * i], cap[2 * i], cost[2 * i], frm[2 * i] = v, c, w * n, u       # 費用を n 倍
        to[2 * i + 1], cap[2 * i + 1], cost[2 * i + 1], frm[2 * i + 1] = u, 0, -w * n, v
        g[u].append(2 * i)
        g[v].append(2 * i + 1)
    excess = list(b)
    p = [0] * n
    eps = max([abs(c) for c in cost] + [1])
    while True:
        eps = max(1, eps // alpha)             # ε を 1/α 倍ずつ小さくし、最後に ε=1 の段を必ず回す
        # (1) 被約費用が負の残余辺をすべて飽和させる → 0-最適の前フロー
        for e in range(2 * m):
            if cap[e] > 0 and cost[e] + p[frm[e]] - p[to[e]] < 0:
                f = cap[e]
                cap[e] = 0
                cap[e ^ 1] += f
                excess[frm[e]] -= f
                excess[to[e]] += f
        # (2) 余りのある頂点から、許容辺（被約費用 < 0）で押し出す。無ければ再ラベル
        cur = [0] * n
        q = deque(v for v in range(n) if excess[v] > 0)
        inq = [excess[v] > 0 for v in range(n)]
        while q:
            u = q.popleft()
            inq[u] = False
            gu = g[u]
            while excess[u] > 0:
                if cur[u] == len(gu):          # 再ラベル: 最も小さい被約費用を -eps にする
                    best = None
                    for e in gu:
                        if cap[e] > 0:
                            t = p[to[e]] - cost[e]
                            if best is None or t > best:
                                best = t
                    p[u] = best - eps
                    cur[u] = 0
                    continue
                e = gu[cur[u]]
                v = to[e]
                if cap[e] > 0 and cost[e] + p[u] - p[v] < 0:
                    f = excess[u] if excess[u] < cap[e] else cap[e]
                    cap[e] -= f
                    cap[e ^ 1] += f
                    excess[u] -= f
                    excess[v] += f
                    if excess[v] > 0 and not inq[v]:
                        inq[v] = True
                        q.append(v)
                    if cap[e] == 0:
                        cur[u] += 1
                else:
                    cur[u] += 1
        if eps == 1:
            break
    return sum((c - cap[2 * i]) * w for i, (u, v, c, w) in enumerate(edges))


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    b = [int(x) for x in data[2:2 + n]]
    edges = []
    p = 2 + n
    for _ in range(m):
        u, v, c, w = int(data[p]) - 1, int(data[p + 1]) - 1, int(data[p + 2]), int(data[p + 3])
        p += 4
        edges.append((u, v, c, w))
    print(min_cost_b_flow(n, edges, b))


if __name__ == "__main__":
    main()