結果

問題 No.1479 Matrix Eraser
ユーザー とりゐ
提出日時 2021-11-11 19:35:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 866 ms / 3,000 ms
コード長 2,213 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 138,036 KB
最終ジャッジ日時 2024-11-23 15:38:02
合計ジャッジ時間 21,297 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

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

from collections import deque
class Dinic:
def __init__(self, n):
self.n = n
self.links = [[] for _ in range(n)]
self.depth = None
self.progress = None
def add_link(self, _from, to, cap):
self.links[_from].append([cap, to, len(self.links[to])])
self.links[to].append([0, _from, len(self.links[_from]) - 1])
def bfs(self, s):
depth = [-1] * self.n
depth[s] = 0
q = deque([s])
while q:
v = q.popleft()
for cap, to, rev in self.links[v]:
if cap > 0 and depth[to] < 0:
depth[to] = depth[v] + 1
q.append(to)
self.depth = depth
def dfs(self, v, t, flow):
if v == t:
return flow
links_v = self.links[v]
for i in range(self.progress[v], len(links_v)):
self.progress[v] = i
cap, to, rev = link = links_v[i]
if cap == 0 or self.depth[v] >= self.depth[to]:
continue
d = self.dfs(to, t, min(flow, cap))
if d == 0:
continue
link[0] -= d
self.links[to][rev][0] += d
return d
return 0
def max_flow(self, s, t):
flow = 0
while True:
self.bfs(s)
if self.depth[t] < 0:
return flow
self.progress = [0] * self.n
current_flow = self.dfs(s, t, float('inf'))
while current_flow > 0:
flow += current_flow
current_flow = self.dfs(s, t, float('inf'))
from collections import defaultdict
h,w=map(int,input().split())
d=defaultdict(list)
for i in range(h):
a=list(map(int,input().split()))
for j in range(w):
if a[j]!=0:
d[a[j]].append((i,h+j))
ans=0
for i in d:
x=set()
y=set()
for xi,yi in d[i]:
x.add(xi)
y.add(yi)
X,Y=len(x),len(y)
mf=Dinic(X+Y+2)
s,t=0,X+Y+1
id=defaultdict(int)
tmp=1
for j in x:
id[j]=tmp
mf.add_link(s,tmp,1)
tmp+=1
for j in y:
id[j]=tmp
mf.add_link(tmp,t,1)
tmp+=1
for xi,yi in d[i]:
mf.add_link(id[xi],id[yi],1)
ans+=mf.max_flow(s,t)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0