結果
問題 |
No.3201 Corporate Synergy
|
ユーザー |
|
提出日時 | 2025-07-14 14:27:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 2,254 bytes |
コンパイル時間 | 354 ms |
コンパイル使用メモリ | 82,640 KB |
実行使用メモリ | 77,516 KB |
最終ジャッジ日時 | 2025-07-14 14:27:53 |
合計ジャッジ時間 | 3,166 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
from collections import deque class Dinic: def __init__(self, n): self.n = n self.links = [[] for _ in range(n)] self.depth = [] self.progress = [] def add_link(self, fr, to, cap): self.links[fr].append([cap, to, len(self.links[to])]) self.links[to].append([0, fr, len(self.links[fr]) - 1]) def max_flow(self, s, t): INF = float('inf') flow = 0 while True: self._bfs(s) if self.depth[t] < 0: return flow self.progress = [0] * self.n current_flow = self._dfs(s, t, INF) while current_flow > 0: flow += current_flow current_flow = self._dfs(s, t, INF) def _bfs(self, s): depth = [-1] * self.n depth[s] = 0 que = deque([s]) while que: v = que.popleft() for cap, to, rev in self.links[v]: if 0 < cap and depth[to] < 0: depth[to] = depth[v] + 1 que.append(to) self.depth = depth def _dfs(self, v, t, flow): if v == t: return flow links_v = self.links[v] for i in range(self.progress[v], len(links_v)): self.progress[v] = i cap, to, rev = link = links_v[i] if cap == 0 or self.depth[to] <= self.depth[v]: continue d = self._dfs(to, t, min(flow, cap)) if d == 0: continue link[0] -= d self.links[to][rev][0] += d return d return 0 INF = 1 << 60 N = int(input()) P = list(map(int, input().split())) M = int(input()) E = [tuple(map(int, input().split())) for _ in range(M)] K = int(input()) ABS = [tuple(map(int, input().split())) for _ in range(K)] g = Dinic(N + K + 2) S, T = N + K, N + K + 1 pp = 0 for i, p in enumerate(P): if p >= 0: g.add_link(S, i, p) pp += p else: g.add_link(i, T, -p) for u, v in E: g.add_link(v - 1, u - 1, INF) ss = 0 for i, (a, b, s) in enumerate(ABS, N): g.add_link(S, i, s) g.add_link(i, a - 1, INF) g.add_link(i, b - 1, INF) ss += s print(pp + ss - g.max_flow(S, T))