結果

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

ソースコード

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

from collections import deque
import sys
sys.setrecursionlimit(10**6)
class MaxFlow:
inf = 10**18
class E:
def __init__(self,to,cap):
self.to = to
self.cap = cap
self.rev = None
def __init__(self,n):
self.n = n
self.graph = [[] for _ in range(n)]
def add_edge(self, fr, to, cap):
graph = self.graph
edge = self.E(to,cap)
edge2 = self.E(fr,0)
edge.rev = edge2
edge2.rev = edge
graph[fr].append(edge)
graph[to].append(edge2)
def bfs(self, s, t):
level = self.level = [self.n]*self.n
q = deque([s])
level[s] = 0
while q:
now = q.popleft()
lw = level[now]+1
for e in self.graph[now]:
if e.cap and level[e.to]> lw:
level[e.to] = lw
if e.to == t:
return True
q.append(e.to)
return False
def dfs(self, s, t, up):
graph = self.graph
it = self.it
level = self.level
st = deque([t])
while st:
v = st[-1]
if v == s:
st.pop()
flow = up
for w in st:
e = graph[w][it[w]].rev
flow = min(flow, e.cap)
for w in st:
e = graph[w][it[w]]
e.cap += flow
e.rev.cap -= flow
return flow
lv = level[v]-1
while it[v] < len(graph[v]):
e = graph[v][it[v]]
re = e.rev
if re.cap == 0 or lv != level[e.to]:
it[v] += 1
continue
st.append(e.to)
break
if it[v] == len(graph[v]):
st.pop()
level[v] = self.n
return 0
def flow(self,s,t,flow_limit=inf):
flow = 0
while flow < flow_limit and self.bfs(s,t):
self.it = [0]*self.n
while flow < flow_limit:
f = self.dfs(s,t,flow_limit-flow)
if f == 0:
break
flow += f
return flow
def min_cut(self,s):
visited = [0]*self.n
q = deque([s])
while q:
v = q.pop()
visited[v] = 1
for e in self.graph[v]:
if e.cap and not visited[e.to]:
q.append(e.to)
return visited
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=MaxFlow(X+Y+2)
s,t=0,X+Y+1
id=defaultdict(int)
tmp=1
for j in x:
id[j]=tmp
mf.add_edge(s,tmp,1)
tmp+=1
for j in y:
id[j]=tmp
mf.add_edge(tmp,t,1)
tmp+=1
for xi,yi in d[i]:
mf.add_edge(id[xi],id[yi],1)
ans+=mf.flow(s,t)
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0