結果

問題 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): # 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)
0