結果
問題 |
No.3201 Corporate Synergy
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:35:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 5,439 bytes |
コンパイル時間 | 486 ms |
コンパイル使用メモリ | 81,604 KB |
実行使用メモリ | 76,772 KB |
最終ジャッジ日時 | 2025-07-11 22:35:50 |
合計ジャッジ時間 | 3,047 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
from __future__ import annotations class Dinic: def __init__(self, N): self.N = N self.G = [[] for i in range(N)] self.A = [] self.C = [] def add_edge(self, frm, to, cap, rcap=0): assert cap >= 0 and rcap >= 0 id = len(self.A) assert id%2 == 0 self.G[frm].append(id) self.G[to].append(id|1) self.A.append(to) self.A.append(frm) self.C.append(cap) self.C.append(rcap) def _dual(self, s, t): G = self.G A = self.A C = self.C from collections import deque assert s != t NIL = -1 depth = [NIL] * self.N Q = deque([s]) depth[s] = 0 while Q: v = Q.popleft() for id in G[v]: a = A[id] cap = C[id] if cap > 0 and depth[a] == NIL: depth[a] = depth[v] + 1 Q.append(a) if depth[t] == NIL: return [] return depth def _primal(self, s, t, depth, it): G = self.G A = self.A C = self.C Q = [s] pi_edge = [] found = False while Q: v = Q[-1] Gv = G[v] while it[v] < len(Gv): id = Gv[it[v]] a = A[id] cap = C[id] if cap > 0 and depth[v] + 1 == depth[a]: Q.append(a) pi_edge.append(id) if a == t: found = True Q.clear() break else: it[v] += 1 else: v = Q.pop() if pi_edge: pi_edge.pop() if Q: it[Q[-1]] += 1 if not found: return 0 w = min(C[id] for id in pi_edge) assert w > 0 cur = t while cur != s: id = pi_edge.pop() C[id] -= w C[id^1] += w cur = A[id^1] return w def flow(self, s, t): assert s != t F = 0 while depth := self._dual(s, t): it = [0]*self.N while dF := self._primal(s, t, depth, it): F += dF return F def __repr__(self, map: dict[str, int]|None = None): # type: ignore inv = {} if map is not None: for k, v in map.items(): inv[v] = k def repr_id(v: int) -> str: if map is None: return str(v) else: return inv[v] res = [] for v in range(self.N): for id in self.G[v]: a = self.A[id] cap = self.C[id] rcap = self.C[id^1] if rcap != 0 and id&1 == 0: res.append(f"{repr_id(v)} -> {repr_id(a)}: {rcap}/{rcap + cap}") return "\n".join(res) class PSP: INF = 10**18 def __init__(self, N: int): self.N = N self.V = N self.types = ["R"]*N self.baseline = 0 self.const = [[0, 0] for _ in range(self.V)] self.rel = [] def _add_vertex(self, type: str) -> int: assert type in ["S", "T", "I"] self.const.append([0, 0]) self.types.append(type) self.V += 1 return self.V - 1 def set_const(self, x, a): assert 0 <= x < self.N self.baseline += a def set_1(self, x, a): if self.types[x] == "R": assert 0 <= x < self.N else: assert 0 <= x < self.V self.const[x][1] += a def set_01(self, x, y, a): assert 0 <= x < self.N assert 0 <= y < self.N if x == y: return assert a <= 0 self.rel.append((x, y, abs(a))) def set_10(self, x, y, a): return self.set_01(y, x, a) def set_matrix(self, x, y, M: list[list[int]]): assert 0 <= x < self.N assert 0 <= y < self.N assert len(M) == 2 assert len(M[0]) == 2 a, b = M[0] c, d = M[1] assert a+d >= b+c self.set_const(x, a) self.set_1(x, c-a) self.set_1(y, d-c) self.set_01(x, y, (b+c) - (a+d)) def max(self): S = self._add_vertex("S") T = self._add_vertex("T") mf = Dinic(self.V) for v in range(self.V): if 0 <= v < self.N: assert self.types[v] == "R" if self.types[v] in ["S", "T"]: continue mf.add_edge(S, v, 0) mf.add_edge(v, T, 0) if self.const[v][0] > 0: self.baseline += self.const[v][0] mf.add_edge(S, v, self.const[v][0]) elif self.const[v][0] < 0: mf.add_edge(v, T, -self.const[v][0]) if self.const[v][1] > 0: self.baseline += self.const[v][1] mf.add_edge(v, T, self.const[v][1]) elif self.const[v][1] < 0: mf.add_edge(S, v, -self.const[v][1]) for x, y, c in self.rel: mf.add_edge(x, y, c) mincut = mf.flow(S, T) return self.baseline - mincut def solve(N, P, M, E, K, ABS): INF = 10**18 psp = PSP(N) for i, p in enumerate(P): psp.set_1(i, p) for u, v in E: psp.set_01(u, v, -INF) for a, b, s in ABS: psp.set_matrix(a, b, [[0, 0], [0, s]]) ans = psp.max() return ans N = int(input()) P = list(map(int, input().split())) M = int(input()) E = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)] K = int(input()) ABS = [] class Read: for _ in range(K): a, b, s = map(int, input().split()) a -= 1 b -= 1 ABS.append((a, b, s)) ans = solve(N, P, M, E, K, ABS) print(ans)