結果
| 問題 | No.1615 Double Down |
| ユーザー |
 iaNTU
|
| 提出日時 | 2021-06-22 02:32:44 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,868 bytes |
| コンパイル時間 | 310 ms |
| コンパイル使用メモリ | 82,480 KB |
| 実行使用メモリ | 135,000 KB |
| 最終ジャッジ日時 | 2024-07-17 15:27:29 |
| 合計ジャッジ時間 | 23,502 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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)
for j in range(l) :
if alivee[j] and not wentx[x[j]] and not wenty[y[j]] and matchx[x[j]] != y[j] :
alivee[j] = False
ans = 0
for i in range(0, k + 1) :
ans += val[i] << i
print(ans)