結果
問題 | No.421 しろくろチョコレート |
ユーザー |
|
提出日時 | 2022-02-24 13:19:35 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,338 bytes |
コンパイル時間 | 298 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 79,664 KB |
最終ジャッジ日時 | 2024-07-02 11:29:34 |
合計ジャッジ時間 | 7,703 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 11 RE * 33 |
ソースコード
#Dinic法で最大流を求める#deque のimport が必要#逆辺追加しなきゃいけないから、#グラフの構成はadd_edgeで行う#最大流は flow メソッドでfrom collections import dequeclass Dinic:def __init__(self,N):self.N = Nself.G = [[] for _ in range(N)]self.level = Noneself.progress = Noneself.edge = []def add_edge(self,fr,to,cap):forward = [to,cap,None]forward[2] = backward = [fr,0,forward]self.G[fr].append(forward)self.G[to].append(backward)self.edge.append(forward)def add_multi_edge(self,v1,v2,cap1,cap2):edge1 = [v2,cap1,None]edge1[2] = edge2 = [v1,cap2,edge1]self.G[v1].append(edge1)self.G[v2].append(edge2)self.edge.append(edge1)def get_edge(self,i):return self.edge[i]# i 回目に追加した辺のポインタを返す# 0-index, 順辺のみdef bfs(self,s,t):self.level = level = [None] * self.Nq = deque([s])level[s] = 0G = self.Gwhile q:v = q.popleft()lv = level[v] + 1for w,cap,_ in G[v]:if cap and level[w] is None:level[w] = lvq.append(w)return level[t] is not Nonedef dfs(self,v,t,f):if v == t:return flevel = self.levelGv = self.G[v]for i in range(self.progress[v],len(Gv)):self.progress[v] = iw,cap,rev = e = Gv[i]if cap and level[v] < level[w]:d = self.dfs(w,t,min(f,cap))if d:e[1] -= drev[1] += dreturn dreturn 0def flow(self,s,t,):flow = 0inf = 1 << 30G = self.Gwhile self.bfs(s,t):self.progress = [0] * self.Nf = infwhile f:f = self.dfs(s,t,inf)flow += freturn flowdef min_cut(self,s):#最小カットを実現する頂点の分割を与える#True なら source側#False なら sink側visited = [False for i in range(self.N)]q = deque([s])while q:now = q.popleft()visited[now] = Truefor to,cap,_ in self.G[now]:if cap and not visited[to]:visited[to] = Trueq.append(to)return visitedN,M = map(int,input().split())S = [input() for _ in range(N)]countb = 0countw = 0dinic = Dinic(N * M + 2)T = N * M + 1def f(h,w):return h * M + w + 1for h in range(N):for w in range(M):if S[h][w] == "w":countw += 1dinic.add_edge(f(h,w),T,1)elif S[h][w] == "b":countb += 1dinic.add_edge(0,f(h,w),1)for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:if 0 <= h + i < N and 0 <= w + j < N:if S[h+i][w+j] == "w":dinic.add_edge(f(h,w),f(h+i,w+j),1)match = dinic.flow(0,T)countb -= matchcountw -= matchnum = min(countw,countb)countb -= numcountw -= numans = 100 * match + 10 * num + countb + countwprint(ans)