Day 170-Q4 — 2026-10-05 | 負の閉路がある最小費用 b-フロー（負のコストの辺を先に容量いっぱい流し、逆辺だけ残すと全辺が非負になる）

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


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]]
    pos = 2 + n
    S, T = n, n + 1
    V = n + 2
    # 残余グラフ: 辺 k の逆辺は k^1
    to, cap, cost, head, nxt = [], [], [], [-1] * V, []

    def add_edge(u, v, c, w):
        to.append(v); cap.append(c); cost.append(w); nxt.append(head[u]); head[u] = len(to) - 1
        to.append(u); cap.append(0); cost.append(-w); nxt.append(head[v]); head[v] = len(to) - 1

    excess = b[:]
    base = 0
    for _ in range(m):
        u, v, c, w = (int(x) for x in data[pos:pos + 4]); pos += 4
        u -= 1; v -= 1
        if w >= 0:
            add_edge(u, v, c, w)
        else:
            # 負の辺は先に容量いっぱい流しておく。残余グラフには v→u（コスト -w > 0）だけが残る
            base += c * w
            excess[u] -= c
            excess[v] += c
            add_edge(v, u, c, -w)
    need = 0
    for v in range(n):
        if excess[v] > 0:
            add_edge(S, v, excess[v], 0)
            need += excess[v]
        elif excess[v] < 0:
            add_edge(v, T, -excess[v], 0)

    # 全辺のコストが非負なので、ポテンシャル 0 から Dijkstra で逐次最短路
    INF = float('inf')
    h = [0] * V
    flow = 0
    total = 0
    while flow < need:
        dist = [INF] * V
        pe = [-1] * V
        dist[S] = 0
        pq = [(0, S)]
        while pq:
            d, u = heappop(pq)
            if d > dist[u]:
                continue
            hu = h[u]
            k = head[u]
            while k != -1:
                if cap[k] > 0:
                    v = to[k]
                    nd = d + cost[k] + hu - h[v]
                    if nd < dist[v]:
                        dist[v] = nd
                        pe[v] = k
                        heappush(pq, (nd, v))
                k = nxt[k]
        if dist[T] == INF:
            print("infeasible")
            return
        for v in range(V):
            if dist[v] < INF:
                h[v] += dist[v]
        f = need - flow
        v = T
        while v != S:
            k = pe[v]
            if cap[k] < f:
                f = cap[k]
            v = to[k ^ 1]
        v = T
        while v != S:
            k = pe[v]
            cap[k] -= f
            cap[k ^ 1] += f
            v = to[k ^ 1]
        flow += f
        total += f * (h[T] - h[S])
    print(base + total)


main()