結果
問題 | No.421 しろくろチョコレート |
ユーザー |
|
提出日時 | 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 |
ソースコード
# Dinicfrom collections import dequeclass maxflow:def __init__(self, n):self.n = nself.G = [[] for i in range(n)] # 隣接グラフself.edges = []self.edge_num = 0self.flow_now = 0self.start = Noneself.terminal = Nonedef add_edge(self, fr, to, cap, cap_rev = 0): # 辺を追加# fr: 始点, to: 終点, cap: 容量, cap_rev = 逆辺容量(すなわち初期流量)edge_num = self.edge_numforward = [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.edgesfor e_id in range(0, self.edge_num<<1, 2):edges[e_id][0] += edges[e_id+1][0]edges[e_id+1][0] = 0self.flow_prv = self.flow_nowself.flow_now = 0def _bfs(self, s, t): # 始点sから各点への最短距離(self.dis)を計算dist = self._dist = [-1]*self.nG = self.Gtask = deque([s])dist[s] = 0while task:p = task.popleft(); d_p = dist[p];d_n = d_p + 1for cap, q, _, _ in G[p]:if cap == 0 or dist[q] >= 0: continuedist[q] = d_ntask.append(q)return dist[t] >= 0def _dfs(self, s, t, flow_limit):dist = self._distit = self._it = [0]*self.nG = self.Gdist_t = dist[t]path = [None]*dist_t # 今まで辿った経路を入れる(逆辺で管理)cap_min = [None]*dist_t+[10**20] # 今の経路において、各深さまでの容量最小値path_len_now = 0ans = 0p = swhile True:if ans == flow_limit: break # 流量上限がある場合、上限に達したら終了if it[p] == len(G[p]): # 全ての辺を見終わっているときif p == s: break # 始点を見終わっているなら終了path_len_now -= 1p = path[path_len_now][1] # 前の辺を伝って戻る(pathには逆辺が入っていることに注意)it[p] += 1 # 次回はこの辺を調べないようにcontinuecap, 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] += 1continue# それ以外の場合は進行可能cap_min[path_len_now] = min(cap, cap_min[path_len_now-1])path[path_len_now] = rev_edge # 逆辺をpathに追加path_len_now += 1p = toif to != t: continue# 終点にたどり着いた時、フローを流すflow = min(flow_limit - ans, min(cap_min))q = tfor 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] -= flowedge[0] -= flowrev_edge[0] += flowq = frans += flowreturn ansdef flow(self, s, t, flow_limit = 10**20): # sからtへの最大流量を計算、O(V^2 E) (flow_limit: 流量上限)if self.start != s or self.terminal != t:self.reset()self.start = s; self.terminal = t;bfs = self._bfsdfs = self._dfsans = 0while bfs(s, t):self.flow_now += dfs(s, t, flow_limit)return self.flow_now # 上限以内で流せた流量を返すdef min_cut(self, s): # 現在のフローにの残余グラフについて、sから行ける点をTrueで返す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_edgereturn {"cap": cap, "flow": now_flow, "from": fr, "to": to}else:returndef get_edges(self): # 全ての辺の状態を取得するans = [None]*self.edge_numfor cap, to, rev_edge, e_id in self.edges[::2]:now_flow, fr, _, _ = rev_edgeans[e_id>>1] = {"cap": cap, "flow": now_flow, "from": fr, "to": to}return ansN, M = map(int,input().split())S = [input() for _ in range(N)]V = N * M + 3s = V - 1t = V - 2mf = maxflow(V)for i in range(N):for j in range(M):par = (i + j) % 2v = i * M + jif par and S[i][j] != ".":mf.add_edge(s, v, 1)if i > 0 and S[i-1][j] != ".":v1 = v - Mmf.add_edge(v, v1, 1)if i < N-1 and S[i+1][j] != ".":v1 = v + Mmf.add_edge(v, v1, 1)if j > 0 and S[i][j-1] != ".":v1 = v - 1mf.add_edge(v, v1, 1)if j < M-1 and S[i][j+1] != ".":v1 = v + 1mf.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_bprint(ans)