#726626 (PyPy3) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	Kento Maeda
提出日時	2021-12-26 15:45:08
言語	PyPy3 (7.3.15)
結果	AC
実行時間	148 ms / 2,000 ms
コード長	5,689 bytes
コンパイル時間	164 ms
コンパイル使用メモリ	81,848 KB
実行使用メモリ	79,596 KB
最終ジャッジ日時	2023-10-24 15:06:09
合計ジャッジ時間	7,172 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	45 ms 55,620 KB
testcase_01	AC	131 ms 78,352 KB
testcase_02	AC	70 ms 72,640 KB
testcase_03	AC	50 ms 63,544 KB
testcase_04	AC	66 ms 70,564 KB
testcase_05	AC	70 ms 70,588 KB
testcase_06	AC	49 ms 61,240 KB
testcase_07	AC	95 ms 77,280 KB
testcase_08	AC	65 ms 68,428 KB
testcase_09	AC	61 ms 68,160 KB
testcase_10	AC	63 ms 68,188 KB
testcase_11	AC	97 ms 77,240 KB
testcase_12	AC	43 ms 55,620 KB
testcase_13	AC	43 ms 55,620 KB
testcase_14	AC	43 ms 55,620 KB
testcase_15	AC	42 ms 55,620 KB
testcase_16	AC	137 ms 79,212 KB
testcase_17	AC	137 ms 79,292 KB
testcase_18	AC	134 ms 79,068 KB
testcase_19	AC	43 ms 55,620 KB
testcase_20	AC	123 ms 78,628 KB
testcase_21	AC	128 ms 78,692 KB
testcase_22	AC	115 ms 77,864 KB
testcase_23	AC	42 ms 55,620 KB
testcase_24	AC	42 ms 55,620 KB
testcase_25	AC	42 ms 55,620 KB
testcase_26	AC	42 ms 55,620 KB
testcase_27	AC	42 ms 55,620 KB
testcase_28	AC	101 ms 77,920 KB
testcase_29	AC	104 ms 77,956 KB
testcase_30	AC	111 ms 77,952 KB
testcase_31	AC	114 ms 79,496 KB
testcase_32	AC	108 ms 77,964 KB
testcase_33	AC	111 ms 77,868 KB
testcase_34	AC	51 ms 63,788 KB
testcase_35	AC	54 ms 66,388 KB
testcase_36	AC	96 ms 77,240 KB
testcase_37	AC	142 ms 79,280 KB
testcase_38	AC	142 ms 79,412 KB
testcase_39	AC	96 ms 77,064 KB
testcase_40	AC	109 ms 77,868 KB
testcase_41	AC	53 ms 63,796 KB
testcase_42	AC	58 ms 66,024 KB
testcase_43	AC	92 ms 77,344 KB
testcase_44	AC	127 ms 78,900 KB
testcase_45	AC	68 ms 70,588 KB
testcase_46	AC	65 ms 70,304 KB
testcase_47	AC	109 ms 77,628 KB
testcase_48	AC	115 ms 79,396 KB
testcase_49	AC	90 ms 77,172 KB
testcase_50	AC	72 ms 72,648 KB
testcase_51	AC	129 ms 78,852 KB
testcase_52	AC	98 ms 77,308 KB
testcase_53	AC	69 ms 71,328 KB
testcase_54	AC	71 ms 72,648 KB
testcase_55	AC	64 ms 70,552 KB
testcase_56	AC	67 ms 70,256 KB
testcase_57	AC	71 ms 70,336 KB
testcase_58	AC	110 ms 77,832 KB
testcase_59	AC	77 ms 73,260 KB
testcase_60	AC	138 ms 79,596 KB
testcase_61	AC	148 ms 79,460 KB
testcase_62	AC	43 ms 55,620 KB
testcase_63	AC	44 ms 55,620 KB
testcase_64	AC	50 ms 63,788 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

# 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): # 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._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): # 現在のフローにの残余グラフについて、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_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)

yukicoder

結果

テストケース

ソースコード