結果
問題 | No.2320 Game World for PvP |
ユーザー |
|
提出日時 | 2024-11-10 23:01:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 235 ms / 2,000 ms |
コード長 | 4,295 bytes |
コンパイル時間 | 1,143 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 81,388 KB |
最終ジャッジ日時 | 2024-11-10 23:01:45 |
合計ジャッジ時間 | 7,267 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
NUMERIC_LIMITS = 10 ** 18import queueclass maxFlow:class edge:def __init__(s, frm, to, cap, flow):s.frm, s.to = frm, tos.cap, s.flow = cap, flowdef __init__(s, n):s._n = ns.g = [[] for _ in range(n)]s.pos = []def add_edge(s, frm, to, cap):m = len(s.pos)s.pos.append([frm, len(s.g[frm])])s.g[frm].append(s._edge(to, len(s.g[to]), cap))s.g[to].append(s._edge(frm,len(s.g[frm]) - 1, 0))return mdef get_edge(s, i):m = len(s.pos)_e = s.g[s.pos[i][0]][s.pos[i][1]]_re = s.g[_e.to][_e.rev]return s.edge(s.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)def edges(s):m = len(s.pos)result = []for i in range(m):result.append(s.get_edge(i))return resultdef change_edge(s, i, new_cap, new_flow):m = len(s.pos)_e = s.g[s.pos[i].to][s.pos[i].rev]_re = s.g[_e.to][_e.rev]_e.cap = new_cap - new_flow_re.cap = new_flowdef flow(self, s, t, flow_limit = NUMERIC_LIMITS):level = [0] * self._niter = [0] * self._ndef bfs():for i in range(self._n):level[i] = -1level[s] = 0que = queue.Queue()que.put(s)while not que.empty():v = que.get()for e in self.g[v]:if e.cap == 0 or level[e.to] >= 0: continuelevel[e.to] = level[v] + 1if e.to == t: returnque.put(e.to)def dfs(v, up):V, UP = v, upL = [(v, up)]R = {}RES = {}while L:v, up = L.pop()if v == s:R[v, up] = upcontinuelevel_v = level[v]if (v, up) not in RES:res, start = 0, iter[v]else:res, start = RES[v, up]flag = Truefor i in range(start, len(self.g[v])):e = self.g[v][i]if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0: continuefirst, second = e.to, min(up - res, self.g[e.to][e.rev].cap)if (first, second) not in R or R[first, second] == None:L.append((v, up))L.append((first, second))RES[v, up] = (res, i)flag = Falsebreakelse:d = R[first, second]R[first, second] = Noneif d <= 0: continueself.g[v][i].cap += dself.g[e.to][e.rev].cap -= dres += dif res == up: breakif flag:R[v, up] = resreturn R[V, UP]#再起ありdef dfsold(this, v, up):if v == s: return upres = 0level_v = level[v]for i in range(iter[v], len(self.g[v])):e = self.g[v][i]if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0: continued = this(this, e.to, min(up - res, self.g[e.to][e.rev].cap))if d <= 0: continueself.g[v][i].cap += dself.g[e.to][e.rev].cap -= dres += dif res == up: breakreturn resflow = 0while flow < flow_limit:bfs()if level[t] == -1: breakfor i in range(self._n): iter[i]while flow < flow_limit:f = dfs(t, flow_limit - flow)if not f: breakflow += freturn flowdef min_cut(self, s):visited = [False] * self._nque = queue.Queue()que.put(s)while not que.empty():p = que.get()visited[p] = Truefor e in self.g[p]:if e.cap and not visited[e.to]:visited[e.to] = Trueque.put(e.to)return visitedclass _edge:def __init__(s, to, rev, cap):s.to, s.rev = to, revs.cap = capN, S, T = list(map(int, input().split()))E = list(map(int, input().split()))R = list(map(int, input().split()))C = [list(map(int, input().split())) for _ in range(N)]flow = maxFlow(N + 2)s = Nt = N + 1inf = 10 ** 18data = [0] * Nfor e in E:e -= 1data[e] = 1for r in R:r -= 1data[r] = 2for i in range(N):if data[i] == 1: flow.add_edge(s, i, inf)else: flow.add_edge(s, i, 0)if data[i] == 2: flow.add_edge(i, t, inf)else: flow.add_edge(s, i, 0)ans = 0for i in range(N):for j in range(N):flow.add_edge(i, j, C[i][j])ans += C[i][j]ans //= 2ans -= flow.flow(s, t)print(ans)