結果

問題 No.421 しろくろチョコレート
ユーザー ああいい
提出日時 2022-02-24 13:21:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 199 ms / 2,000 ms
コード長 3,338 bytes
コンパイル時間 320 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 79,856 KB
最終ジャッジ日時 2024-07-02 11:30:06
合計ジャッジ時間 8,504 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

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

#Dinic
#deque import
#
#add_edge
# flow
from collections import deque
class Dinic:
def __init__(self,N):
self.N = N
self.G = [[] for _ in range(N)]
self.level = None
self.progress = None
self.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.N
q = deque([s])
level[s] = 0
G = self.G
while q:
v = q.popleft()
lv = level[v] + 1
for w,cap,_ in G[v]:
if cap and level[w] is None:
level[w] = lv
q.append(w)
return level[t] is not None
def dfs(self,v,t,f):
if v == t:return f
level = self.level
Gv = self.G[v]
for i in range(self.progress[v],len(Gv)):
self.progress[v] = i
w,cap,rev = e = Gv[i]
if cap and level[v] < level[w]:
d = self.dfs(w,t,min(f,cap))
if d:
e[1] -= d
rev[1] += d
return d
return 0
def flow(self,s,t,):
flow = 0
inf = 1 << 30
G = self.G
while self.bfs(s,t):
self.progress = [0] * self.N
f = inf
while f:
f = self.dfs(s,t,inf)
flow += f
return flow
def 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] = True
for to,cap,_ in self.G[now]:
if cap and not visited[to]:
visited[to] = True
q.append(to)
return visited
N,M = map(int,input().split())
S = [input() for _ in range(N)]
countb = 0
countw = 0
dinic = Dinic(N * M + 2)
T = N * M + 1
def f(h,w):
return h * M + w + 1
for h in range(N):
for w in range(M):
if S[h][w] == "w":
countw += 1
dinic.add_edge(f(h,w),T,1)
elif S[h][w] == "b":
countb += 1
dinic.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 < M:
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 -= match
countw -= match
num = min(countw,countb)
countb -= num
countw -= num
ans = 100 * match + 10 * num + countb + countw
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0