結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
68,480 KB
testcase_01 AC 77 ms
68,480 KB
testcase_02 AC 77 ms
68,096 KB
testcase_03 AC 81 ms
68,608 KB
testcase_04 AC 201 ms
80,768 KB
testcase_05 AC 130 ms
79,616 KB
testcase_06 AC 151 ms
80,256 KB
testcase_07 AC 132 ms
79,616 KB
testcase_08 AC 136 ms
80,000 KB
testcase_09 AC 173 ms
80,896 KB
testcase_10 AC 125 ms
79,232 KB
testcase_11 AC 147 ms
79,872 KB
testcase_12 AC 166 ms
80,768 KB
testcase_13 AC 112 ms
78,848 KB
testcase_14 AC 173 ms
80,896 KB
testcase_15 AC 131 ms
80,000 KB
testcase_16 AC 151 ms
80,128 KB
testcase_17 AC 145 ms
79,872 KB
testcase_18 AC 235 ms
81,388 KB
testcase_19 AC 159 ms
80,256 KB
testcase_20 AC 161 ms
80,768 KB
testcase_21 AC 131 ms
80,128 KB
testcase_22 AC 165 ms
80,896 KB
testcase_23 AC 166 ms
80,896 KB
testcase_24 AC 138 ms
79,872 KB
testcase_25 AC 140 ms
80,128 KB
testcase_26 AC 152 ms
80,000 KB
testcase_27 AC 80 ms
68,096 KB
testcase_28 AC 177 ms
80,768 KB
testcase_29 AC 175 ms
80,896 KB
testcase_30 AC 196 ms
80,768 KB
testcase_31 AC 179 ms
80,640 KB
testcase_32 AC 78 ms
68,352 KB
testcase_33 AC 183 ms
80,896 KB
権限があれば一括ダウンロードができます

ソースコード

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)
0