Day 172-Q4 — 2026-10-08 | 容量スケーリング法の最小費用 b-フロー（Δ を半分にしながら Δ 単位で送る。負の費用・負の閉路も Δ ごとの飽和で処理）

📋 コピーimport sys
from heapq import heappush, heappop


def solve(n, b, edges):
    # 残余グラフは配列で持つ: 辺 i と i^1 が互いに逆辺
    head = [[] for _ in range(n)]
    to, cap, cost = [], [], []
    for u, v, c, w in edges:
        head[u].append(len(to)); to.append(v); cap.append(c); cost.append(w)
        head[v].append(len(to)); to.append(u); cap.append(0); cost.append(-w)
    ex = b[:]                                   # 各頂点の余剰（正 = まだ送り出す量）
    pot = [0] * n                               # ポテンシャル p。被約費用 = cost + p[u] - p[v]
    U = max([c for _, _, c, _ in edges] + [abs(x) for x in b] + [1])
    delta = 1 << (U.bit_length() - 1)
    INF = float('inf')
    total = 0
    while delta >= 1:
        # (1) 残余 delta 以上で被約費用が負の辺を飽和させる（delta 残余グラフの被約費用を非負にする）
        for u in range(n):
            for e in head[u]:
                r = cap[e]
                if r >= delta and cost[e] + pot[u] - pot[to[e]] < 0:
                    cap[e] = 0
                    cap[e ^ 1] += r
                    ex[u] -= r
                    ex[to[e]] += r
                    total += r * cost[e]
        # (2) 余剰 >= delta の頂点から不足 <= -delta の頂点へ、delta ずつ最短路で送る
        while True:
            srcs = [v for v in range(n) if ex[v] >= delta]
            if not srcs or not any(ex[v] <= -delta for v in range(n)):
                break
            dist = [INF] * n
            prev = [-1] * n
            hq = []
            for s in srcs:
                dist[s] = 0
                hq.append((0, s))
            t = -1
            while hq:
                d, u = heappop(hq)
                if d > dist[u]:
                    continue
                if ex[u] <= -delta:             # 最初に取り出された不足頂点で打ち切る
                    t = u
                    break
                pu = pot[u]
                for e in head[u]:
                    if cap[e] >= delta:
                        v = to[e]
                        nd = d + cost[e] + pu - pot[v]
                        if nd < dist[v]:
                            dist[v] = nd
                            prev[v] = e
                            heappush(hq, (nd, v))
            if t < 0:
                break                           # この delta ではもう送れない
            dt = dist[t]
            for v in range(n):                  # p += min(d, d_t): 届かなかった頂点も d_t で打ち切る
                pot[v] += dist[v] if dist[v] < dt else dt
            v = t
            while prev[v] >= 0:
                e = prev[v]
                cap[e] -= delta; cap[e ^ 1] += delta
                total += delta * cost[e]
                v = to[e ^ 1]
            ex[v] -= delta; ex[t] += delta
        delta >>= 1
    if any(ex):
        return None
    return total


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 = []
    k = 2 + n
    for _ in range(m):
        u, v, c, w = (int(x) for x in data[k:k + 4])
        k += 4
        edges.append((u - 1, v - 1, c, w))
    ans = solve(n, b, edges)
    print("infeasible" if ans is None else ans)


if __name__ == "__main__":
    main()