結果

問題 No.2320 Game World for PvP
ユーザー D.F.ナス太郎D.F.ナス太郎
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

NUMERIC_LIMITS = 10 ** 18
import queue
class maxFlow:
class edge:
def __init__(s, frm, to, cap, flow):
s.frm, s.to = frm, to
s.cap, s.flow = cap, flow
def __init__(s, n):
s._n = n
s.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 m
def 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 result
def 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_flow
def flow(self, s, t, flow_limit = NUMERIC_LIMITS):
level = [0] * self._n
iter = [0] * self._n
def bfs():
for i in range(self._n):
level[i] = -1
level[s] = 0
que = 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: continue
level[e.to] = level[v] + 1
if e.to == t: return
que.put(e.to)
def dfs(v, up):
V, UP = v, up
L = [(v, up)]
R = {}
RES = {}
while L:
v, up = L.pop()
if v == s:
R[v, up] = up
continue
level_v = level[v]
if (v, up) not in RES:
res, start = 0, iter[v]
else:
res, start = RES[v, up]
flag = True
for 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: continue
first, 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 = False
break
else:
d = R[first, second]
R[first, second] = None
if d <= 0: continue
self.g[v][i].cap += d
self.g[e.to][e.rev].cap -= d
res += d
if res == up: break
if flag:
R[v, up] = res
return R[V, UP]
#
def dfsold(this, v, up):
if v == s: return up
res = 0
level_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: continue
d = this(this, e.to, min(up - res, self.g[e.to][e.rev].cap))
if d <= 0: continue
self.g[v][i].cap += d
self.g[e.to][e.rev].cap -= d
res += d
if res == up: break
return res
flow = 0
while flow < flow_limit:
bfs()
if level[t] == -1: break
for i in range(self._n): iter[i]
while flow < flow_limit:
f = dfs(t, flow_limit - flow)
if not f: break
flow += f
return flow
def min_cut(self, s):
visited = [False] * self._n
que = queue.Queue()
que.put(s)
while not que.empty():
p = que.get()
visited[p] = True
for e in self.g[p]:
if e.cap and not visited[e.to]:
visited[e.to] = True
que.put(e.to)
return visited
class _edge:
def __init__(s, to, rev, cap):
s.to, s.rev = to, rev
s.cap = cap
N, 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 = N
t = N + 1
inf = 10 ** 18
data = [0] * N
for e in E:
e -= 1
data[e] = 1
for r in R:
r -= 1
data[r] = 2
for 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 = 0
for i in range(N):
for j in range(N):
flow.add_edge(i, j, C[i][j])
ans += C[i][j]
ans //= 2
ans -= flow.flow(s, t)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0