提出 #17761215

---

ソースコード 拡げる

import sys
import numpy as np
import networkx as nx

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

INF = 1 << 30

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

def main(N, M, A, B, UV):
    UV = UV - 1
    G = nx.DiGraph()
    source = N
    sink = N + 1
    add_minus = [0] * N
    add_plus = [0] * N
    base_score = 0
    for i in range(N):
        a, b = A[i], B[i]
        x, y, z = -a, -b, b  # 破壊、マイナスでとる、プラスでとる
        m = min(x, y, z)
        if m == x:
            mm = max(y, z)
            base_score += mm
            G.add_edge(source, i, capacity=mm - y)
            G.add_edge(i, sink, capacity=mm - z)
            add_minus[i] = add_plus[i] = 1
        elif m == y:
            mm = max(x, z)
            base_score += mm
            G.add_edge(source, i, capacity=mm - x)
            G.add_edge(i, sink, capacity=mm - z)
            add_plus[i] = 1
        elif m == z:
            mm = max(x, y)
            base_score += mm
            G.add_edge(source, i, capacity=mm - y)  # マイナス
            G.add_edge(i, sink, capacity=mm - x)  # こわす
            add_minus[i] = 1
    for i in range(len(UV)):
        u, v = UV[i]
        for _ in range(2):
            u, v = v, u
            if add_minus[u] and add_plus[v]:
                G.add_edge(v, u, capacity=INF)
    flow = nx.maximum_flow_value(G, source, sink)
    return base_score - flow

N, M = map(int, readline().split())
A = from_readline()
B = from_readline()
G = from_read().reshape(M, 2)

print(main(N, M, A, B, G))

提出情報

ジャッジ結果