P1.1

description

给定 \(N\times M\) 的有障碍网格，每次覆盖同行或同列连续若干。求最少几次使得每处被覆盖正好一次

solution

黑白染色：

• 对于每个黑点 \(i\)：\(S\overset{f=1}{\to}i\overset{f=1}{\to}\begin{cases}i'\\i''\end{cases}\)

• 对于每个白点 \(j\)：\(\begin{cases}j'\\j''\end{cases}\overset{f=1}{\to}j\overset{f=1}{\to}T\)；

• 对于相邻的黑点 \(i\) 和白点 \(j\)：\(i'\overset{f=1}{\to}j'\)，\(i''\overset{f=1}{\to}j''\)。

\(Ans=\sum blank-MaxFlow\)。