結果
問題 | No.1615 Double Down |
ユーザー | iaNTU |
提出日時 | 2021-06-22 02:28:14 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,724 bytes |
コンパイル時間 | 234 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 137,420 KB |
最終ジャッジ日時 | 2024-07-17 15:25:39 |
合計ジャッジ時間 | 23,090 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | -- | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
testcase_50 | -- | - |
testcase_51 | -- | - |
testcase_52 | -- | - |
testcase_53 | -- | - |
testcase_54 | -- | - |
testcase_55 | -- | - |
testcase_56 | -- | - |
ソースコード
from collections import deque class mf_graph: def __init__(self, N) : self.size = N self.g = [[] for i in range(self.size)] self.gsz = [0 for i in range(self.size)] def add_edge(self, u, v, c) : self.g[u].append((v, len(self.g[v]), c)) self.g[v].append((u, len(self.g[u]) - 1, 0)) def Bfs(self, s, t) : q = [] self.went[s] = t self.Iter[s] = self.dep[s] = 0 q.append(s) while len(q) : now = q.pop() for i in self.g[now] : if i[2] and self.went[i[0]] != t : self.went[i[0]] = t self.dep[i[0]] = self.dep[now] + 1 self.Iter[i[0]] = 0 q.append(i[0]) def Dfs(self, u, t, nv) : if u == t : return nv while self.Iter[u] < self.gsz[u] : i = self.Iter[u] if self.g[u][i][2] > 0 and self.dep[self.g[u][i][0]] > self.dep[u] : tmp = self.Dfs(self.g[u][i][0], t, min(self.g[u][i][2], nv)) if tmp > 0 : self.g[u][i] = (self.g[u][i][0], self.g[u][i][1], self.g[u][i][2] - tmp) self.g[self.g[u][i][0]][self.g[u][i][1]] = (self.g[self.g[u][i][0]][self.g[u][i][1]][0], self.g[self.g[u][i][0]][self.g[u][i][1]][1], self.g[self.g[u][i][0]][self.g[u][i][1]][2] + tmp) return tmp self.Iter[u] += 1 return 0 def flow(self, s, t) : self.dep = [0 for i in range(self.size)] self.went = [0 for i in range(self.size)] self.Iter = [0 for i in range(self.size)] for i in range(self.size) : self.gsz[i] = len(self.g[i]) cnt = self.went[s] ans = 0; kInf = 1 << 30 while True : cnt += 1 self.Bfs(s, cnt) if self.went[s] != self.went[t] : break f = 0 while True : f = self.Dfs(s, t, kInf) if f > 0 : ans += f else : break return ans n, m, k, l = map(int, input().split()) x = [0] * l; y = [0] * l; z = [0] * l for i in range(l) : x[i], y[i], z[i] = map(int, input().split()) edges = [[] for i in range(k + 1)] for i in range(l) : edges[z[i]].append(i) alivex = [True] * (n + 1) alivey = [True] * (m + 1) alivee = [False] * l wentx = [False] * (n + 1) wenty = [False] * (m + 1) val = [0] * (k + 1) matchx = [0] * (n + 1) matchy = [0] * (m + 1) S = 0; T = n + m + 1 G = mf_graph(n + m + 2) for j in range(1, n + 1) : G.add_edge(S, j, 1) for j in range(1, m + 1) : G.add_edge(j + n, T, 1) for i in range(k, -1, -1) : for j in edges[i] : if alivex[x[j]] and alivey[y[j]] : alivee[j] = True G.add_edge(x[j], y[j] + n, 1) gx = [[] for j in range(n + 1)] gy = [[] for j in range(m + 1)] for j in range(l) : if alivee[j] : gx[x[j]].append(y[j]) gy[y[j]].append(x[j]) val[i] = G.flow(S, T) for j in range(1, n + 1) : matchx[j] = -1 for j in range(1, m + 1) : matchy[j] = -1 for j in range(1, n + 1) : wentx[j] = False for j in range(1, m + 1) : wenty[j] = False for j in range(1, n + 1) : for e in G.g[j] : if e[0] != S and e[2] == 0 : matchx[j] = e[0] - n matchy[e[0] - n] = j qu = [] for j in range(1, n + 1) : if matchx[j] < 0 : wentx[j] = True qu.append(j) while len(qu) : idx = qu.pop() for j in gx[idx] : if not wentx[matchy[j]] : wentx[matchy[j]] = True qu.append(matchy[j]) for j in range(1, n + 1) : if not wentx[j] : alivex[j] = False for j in range(1, m + 1) : if matchy[j] < 0 : wenty[j] = True qu.append(j) while len(qu) : idx = qu.pop() for j in gy[idx] : if not wenty[matchx[j]] : wenty[matchx[j]] = True qu.append(matchx[j]) for j in range(1, m + 1) : if not wenty[j] : alivey[j] = False for j in range(1, n + 1) : if not wentx[j] : for idx in range(G.gsz[j]) : e = G.g[j][idx] if e[2] >= 0 and e[0] != S and not wenty[e[0] - n] and matchx[j] != e[0] - n : G.g[j][idx] = (G.g[j][idx][0], G.g[j][idx][1], -1) G.g[e[0]][e[1]] = (G.g[e[0]][e[1]][0], G.g[e[0]][e[1]][1], -1) ans = 0 for i in range(0, k + 1) : ans += val[i] << i print(ans)