Day 168-Q4 — 2026-10-03 | 最大重み閉包（燃やす埋める問題。最小カットで最大値を、残余グラフの到達集合で「最小の選び方」を復元）

📋 コピーimport sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    w = [int(v) for v in data[2:2 + n]]
    S, T = n, n + 1
    V = n + 2
    to, cap, head, nxt = [], [], [-1] * V, []

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

    INF = 1 << 60
    total = 0
    for i in range(n):
        if w[i] > 0:
            total += w[i]
            add(S, i, w[i])             # 選べば得られる利益: 切られたら損
        elif w[i] < 0:
            add(i, T, -w[i])            # 選べば払う費用
    for e in range(m):
        a, b = int(data[2 + n + 2 * e]) - 1, int(data[3 + n + 2 * e]) - 1
        add(a, b, INF)                  # a を選ぶなら b も必須（a -> b を切れない辺に）

    flow = 0
    while True:
        level = [-1] * V
        level[S] = 0
        q = deque([S])
        while q:
            u = q.popleft()
            e = head[u]
            while e != -1:
                if cap[e] > 0 and level[to[e]] < 0:
                    level[to[e]] = level[u] + 1
                    q.append(to[e])
                e = nxt[e]
        if level[T] < 0:
            break
        it = head[:]
        while True:
            # 反復的 DFS で増加路を 1 本ずつ探す
            path = []
            u = S
            while u != T:
                e = it[u]
                while e != -1 and not (cap[e] > 0 and level[to[e]] == level[u] + 1):
                    e = nxt[e]
                it[u] = e
                if e == -1:
                    if not path:
                        break
                    level[u] = -1       # 行き止まり。この頂点はもう使わない
                    e = path.pop()
                    u = to[e ^ 1]
                    continue
                path.append(e)
                u = to[e]
            if u != T:
                break
            f = min(cap[e] for e in path)
            for e in path:
                cap[e] -= f
                cap[e ^ 1] += f
            flow += f
    # 残余グラフで S から届く頂点 = 最小カットの S 側のうち最小のもの = 最小の最適な選び方
    seen = [False] * V
    seen[S] = True
    st = [S]
    while st:
        u = st.pop()
        e = head[u]
        while e != -1:
            if cap[e] > 0 and not seen[to[e]]:
                seen[to[e]] = True
                st.append(to[e])
            e = nxt[e]
    print(total - flow, sum(seen[:n]))


main()