結果

問題 No.421 しろくろチョコレート
ユーザー Kento Maeda
提出日時 2021-12-26 15:45:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 142 ms / 2,000 ms
コード長 5,689 bytes
コンパイル時間 327 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 79,908 KB
最終ジャッジ日時 2024-09-23 07:33:23
合計ジャッジ時間 7,114 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

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

# Dinic
from collections import deque
class maxflow:
def __init__(self, n):
self.n = n
self.G = [[] for i in range(n)] #
self.edges = []
self.edge_num = 0
self.flow_now = 0
self.start = None
self.terminal = None
def add_edge(self, fr, to, cap, cap_rev = 0): #
# fr: , to: , cap: , cap_rev =
edge_num = self.edge_num
forward = [cap, to, None, edge_num<<1]
forward[2] = backward = [cap_rev, fr, forward, (edge_num<<1) + 1]
self.edges.append(forward)
self.edges.append(backward)
self.edge_num += 1
# : [, , , ]
self.G[fr].append(forward)
self.G[to].append(backward)
def reset(self): #
edges = self.edges
for e_id in range(0, self.edge_num<<1, 2):
edges[e_id][0] += edges[e_id+1][0]
edges[e_id+1][0] = 0
self.flow_prv = self.flow_now
self.flow_now = 0
def _bfs(self, s, t): # s(self.dis)
dist = self._dist = [-1]*self.n
G = self.G
task = deque([s])
dist[s] = 0
while task:
p = task.popleft(); d_p = dist[p];
d_n = d_p + 1
for cap, q, _, _ in G[p]:
if cap == 0 or dist[q] >= 0: continue
dist[q] = d_n
task.append(q)
return dist[t] >= 0
def _dfs(self, s, t, flow_limit):
dist = self._dist
it = self._it = [0]*self.n
G = self.G
dist_t = dist[t]
path = [None]*dist_t # 辿
cap_min = [None]*dist_t+[10**20] #
path_len_now = 0
ans = 0
p = s
while True:
if ans == flow_limit: break #
if it[p] == len(G[p]): #
if p == s: break #
path_len_now -= 1
p = path[path_len_now][1] # (path)
it[p] += 1 # 調
continue
cap, to, rev_edge, _ = next_edge = G[p][it[p]]
#print(" next_edge :", next_edge, "depth :", dist[p], "->", dist[to])
# t
if cap == 0 or (dist[p] >= dist[to]) or (to != t and dist[p] == dist_t-1):
it[p] += 1
continue
#
cap_min[path_len_now] = min(cap, cap_min[path_len_now-1])
path[path_len_now] = rev_edge # path
path_len_now += 1
p = to
if to != t: continue
#
flow = min(flow_limit - ans, min(cap_min))
q = t
for d in range(dist_t-1,-1,-1):
_, fr, edge, _ = rev_edge = path[d]
cap = edge[0]
if cap == flow: #
it[fr] += 1 # 調
path_len_now = d # path
p = fr
#
cap_min[d] -= flow
edge[0] -= flow
rev_edge[0] += flow
q = fr
ans += flow
return ans
def flow(self, s, t, flow_limit = 10**20): # stO(V^2 E) (flow_limit: )
if self.start != s or self.terminal != t:
self.reset()
self.start = s; self.terminal = t;
bfs = self._bfs
dfs = self._dfs
ans = 0
while bfs(s, t):
self.flow_now += dfs(s, t, flow_limit)
return self.flow_now #
def min_cut(self, s): # sTrue
self._bfs(s, t=-1)
return [a >= 0 for a in self._dist]
def get_edge(self, edge_idx): # edge_idx
if 0 <= edge_idx < self.edge_num:
cap, to, rev_edge, _ = self.edges[edge_idx<<1]
now_flow, fr, _, _ = rev_edge
return {"cap": cap, "flow": now_flow, "from": fr, "to": to}
else:
return
def get_edges(self): #
ans = [None]*self.edge_num
for cap, to, rev_edge, e_id in self.edges[::2]:
now_flow, fr, _, _ = rev_edge
ans[e_id>>1] = {"cap": cap, "flow": now_flow, "from": fr, "to": to}
return ans
N, M = map(int,input().split())
S = [input() for _ in range(N)]
V = N * M + 3
s = V - 1
t = V - 2
mf = maxflow(V)
for i in range(N):
for j in range(M):
par = (i + j) % 2
v = i * M + j
if par and S[i][j] != ".":
mf.add_edge(s, v, 1)
if i > 0 and S[i-1][j] != ".":
v1 = v - M
mf.add_edge(v, v1, 1)
if i < N-1 and S[i+1][j] != ".":
v1 = v + M
mf.add_edge(v, v1, 1)
if j > 0 and S[i][j-1] != ".":
v1 = v - 1
mf.add_edge(v, v1, 1)
if j < M-1 and S[i][j+1] != ".":
v1 = v + 1
mf.add_edge(v, v1, 1)
elif S[i][j] != ".":
mf.add_edge(v, t, 1)
F = mf.flow(s, t)
ct_w = sum([list(s).count("w") for s in S])
ct_b = sum([list(s).count("b") for s in S])
ans = 90 * F + min(ct_w, ct_b) * 8 + ct_w + ct_b
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0