結果
問題 | 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 |
ソースコード
from collections import dequeclass Dinic:def __init__(self, n):self.n = nself.links = [[] for _ in range(n)]self.depth = Noneself.progress = Nonedef 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.ndepth[s] = 0q = 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] + 1q.append(to)self.depth = depthdef dfs(self, v, t, flow):if v == t:return flowlinks_v = self.links[v]for i in range(self.progress[v], len(links_v)):self.progress[v] = icap, to, rev = link = links_v[i]if cap == 0 or self.depth[v] >= self.depth[to]:continued = self.dfs(to, t, min(flow, cap))if d == 0:continuelink[0] -= dself.links[to][rev][0] += dreturn dreturn 0def max_flow(self, s, t):flow = 0while True:self.bfs(s)if self.depth[t] < 0:return flowself.progress = [0] * self.ncurrent_flow = self.dfs(s, t, float('inf'))while current_flow > 0:flow += current_flowcurrent_flow = self.dfs(s, t, float('inf'))from 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=Dinic(X+Y+2)s,t=0,X+Y+1id=defaultdict(int)tmp=1for j in x:id[j]=tmpmf.add_link(s,tmp,1)tmp+=1for j in y:id[j]=tmpmf.add_link(tmp,t,1)tmp+=1for xi,yi in d[i]:mf.add_link(id[xi],id[yi],1)ans+=mf.max_flow(s,t)print(ans)