燃やす埋める問題。（に必ずしも帰着しなくてもいいけど、自分が知ってるフォーマットに当てはめるにはそれが近かった）
まず、監視カメラは、上か左が壁かグリッド外である空きマスに、下か右を向けて置くと考えてよい。
.#...←....#.. ここに左向きのカメラを設置するくらいなら
.#.......←#.. こう設置した方が絶対にいいし、
.#→.......#.. それはこう設置するのと全く変わらない。上下も一緒
すると各マスにつき「下方向に監視されるならこの監視カメラ」「右方向ならこのカメラ」というのが一意に決まる。
このようなカメラを、マス $c$ に対し、それぞれ $D(c),R(c)$ とする。
カメラ候補を頂点として、「使う」「使わない」の燃やす埋める問題として考える。
1#2
345
,--0-- →1 --1--, S側に属する: 使う
| | T側に属する: 使わない
|--0-- →2 --1--|
| |
S---0-- →3 --1---T
| |
|--0-- ↓1 --1--|
| |
|--0-- ↓2 --1--|
| |
`--0-- ↓4 --1--'
で、監視されないマスがあってはいけないので、各マス $c$ につき、
「$D(c)$ と $R(c)$ がともに「使わない」であってはいけない（コスト無限大）」という制約を課したい。
一般的な燃やす埋めるでは、2つの頂点が違う側に属した時のコストは設定できるが、同じ側に属したときは設定できない。
だが今回の場合は下向きカメラと右向きカメラの間にしか辺が張られないことが明らかなので
（下向き同士、右向き同士に制約は課されないので）、
どちらか（例えば下向き）だけ、「使う」「使わない」の意味合いを反転させてしまえばよい。
,--0-- →1 --1--, ┐
| | │S側に属する: 使う
|--0-- →2 --1--| │T側に属する: 使わない
| | │
S---0-- →3 --1---T ┘
| |
|--1-- ↓1 --0--| ┐
| | │S側に属する: 使わない
|--1-- ↓2 --0--| │T側に属する: 使う
| | │
`--1-- ↓4 --0--' ┘
こうした上で、例えば「→1と↓2がともに使わないであってはいけない」なら、
↓2から→1にコスト無限大の辺を張ることで制約が表現できる。
$S→T$ に最大流を流せば答え。
Python3
from collections import deque
from typing import Tuple, List
class Dinic:
"""
Usage:
mf = Dinic(n)
-> mf.add_link(from, to, capacity)
-> mf.max_flow(source, target)
"""
def __init__(self, n: int):
self.n = n
self.links: List[List[List[int]]] = [[] for _ in range(n)]
# if exists an edge (v→u, capacity)...
# links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]
def add_link(self, from_: int, to: int, capacity: int) -> None:
self.links[from_].append([capacity, to, len(self.links[to]), 1])
self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])
def bfs(self, s: int) -> List[int]:
depth = [-1] * self.n
depth[s] = 0
q = deque([s])
while q:
v = q.popleft()
for cap, to, rev, _ in self.links[v]:
if cap > 0 and depth[to] < 0:
depth[to] = depth[v] + 1
q.append(to)
return depth
def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
links = self.links
stack = [s]
while stack:
v = stack[-1]
if v == t:
break
for i in range(progress[v], link_counts[v]):
progress[v] = i
cap, to, rev, _ = links[v][i]
if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
continue
stack.append(to)
break
else:
progress[v] += 1
stack.pop()
else:
return 0
f = 1 << 60
fwd_links = []
bwd_links = []
for v in stack[:-1]:
cap, to, rev, _ = link = links[v][progress[v]]
f = min(f, cap)
fwd_links.append(link)
bwd_links.append(links[to][rev])
for link in fwd_links:
link[0] -= f
for link in bwd_links:
link[0] += f
return f
def max_flow(self, s: int, t: int) -> int:
link_counts = list(map(len, self.links))
flow = 0
while True:
depth = self.bfs(s)
if depth[t] < 0:
break
progress = [0] * self.n
current_flow = self.dfs(s, t, depth, progress, link_counts)
while current_flow > 0:
flow += current_flow
current_flow = self.dfs(s, t, depth, progress, link_counts)
return flow
def cut_edges(self, s: int) -> List[Tuple[int, int]]:
""" max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
q = [s]
reachable = [0] * self.n
reachable[s] = 1
while q:
v = q.pop()
for cap, u, li, _ in self.links[v]:
if cap == 0 or reachable[u]:
continue
reachable[u] = 1
q.append(u)
edges = []
for v in range(self.n):
if reachable[v] == 0:
continue
for cap, u, li, orig in self.links[v]:
if orig == 1 and reachable[u] == 0:
edges.append((v, u))
return edges
h, w = map(int, input().split())
field = [input() for _ in range(h)]
cells = set()
cameras = set()
camera_ud = [-1] * (h * w)
camera_lr = [-1] * (h * w)
for i in range(h):
for j in range(w):
if field[i][j] == '#':
continue
key = i * w + j
cells.add(key)
if i == 0 or field[i - 1][j] == '#':
camera_key = key << 1
camera_ud[key] = camera_key
cameras.add(camera_key)
else:
camera_ud[key] = camera_ud[key - w]
if j == 0 or field[i][j - 1] == '#':
camera_key = (key << 1) + 1
camera_lr[key] = camera_key
cameras.add(camera_key)
else:
camera_lr[key] = camera_lr[key - 1]
n = len(cameras)
s = n
t = s + 1
mf = Dinic(n + 2)
camera_idx = {c: i for i, c in enumerate(cameras)}
INF = 1 << 60
for key in cameras:
u = camera_idx[key]
if key & 1:
mf.add_link(u, t, 1)
else:
mf.add_link(s, u, 1)
for key in cells:
u = camera_idx[camera_ud[key]]
v = camera_idx[camera_lr[key]]
mf.add_link(u, v, INF)
ans = mf.max_flow(s, t)
print(ans)
