結果
問題 | 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 |
ソースコード
from collections import dequeimport syssys.setrecursionlimit(10**6)class MaxFlow:inf = 10**18class E:def __init__(self,to,cap):self.to = toself.cap = capself.rev = Nonedef __init__(self,n):self.n = nself.graph = [[] for _ in range(n)]def add_edge(self, fr, to, cap):graph = self.graphedge = self.E(to,cap)edge2 = self.E(fr,0)edge.rev = edge2edge2.rev = edgegraph[fr].append(edge)graph[to].append(edge2)def bfs(self, s, t):level = self.level = [self.n]*self.nq = deque([s])level[s] = 0while q:now = q.popleft()lw = level[now]+1for e in self.graph[now]:if e.cap and level[e.to]> lw:level[e.to] = lwif e.to == t:return Trueq.append(e.to)return Falsedef dfs(self, s, t, up):graph = self.graphit = self.itlevel = self.levelst = deque([t])while st:v = st[-1]if v == s:st.pop()flow = upfor w in st:e = graph[w][it[w]].revflow = min(flow, e.cap)for w in st:e = graph[w][it[w]]e.cap += flowe.rev.cap -= flowreturn flowlv = level[v]-1while it[v] < len(graph[v]):e = graph[v][it[v]]re = e.revif re.cap == 0 or lv != level[e.to]:it[v] += 1continuest.append(e.to)breakif it[v] == len(graph[v]):st.pop()level[v] = self.nreturn 0def flow(self,s,t,flow_limit=inf):flow = 0while flow < flow_limit and self.bfs(s,t):self.it = [0]*self.nwhile flow < flow_limit:f = self.dfs(s,t,flow_limit-flow)if f == 0:breakflow += freturn flowdef min_cut(self,s):visited = [0]*self.nq = deque([s])while q:v = q.pop()visited[v] = 1for e in self.graph[v]:if e.cap and not visited[e.to]:q.append(e.to)return visitedfrom collections import defaultdicth,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=0for 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+1id=defaultdict(int)tmp=1for j in x:id[j]=tmpmf.add_edge(s,tmp,1)tmp+=1for j in y:id[j]=tmpmf.add_edge(tmp,t,1)tmp+=1for xi,yi in d[i]:mf.add_edge(id[xi],id[yi],1)ans+=mf.flow(s,t)print(ans)