ALPC의 해설 기사가 없었기 때문에 씁니다. 작성하지 않은 문제에 대해서는 나중에 추가합니다.

ALPC

AtCoder Library (ACL) 테스트를위한 컨테스트입니다.
h tps // 아 t 여기 r. jp / 이렇게 sts / p 등 c 치세 2 /

D - Maxflow

문제문

$ N $ 행 $ M $ 열의 매스 눈이 있습니다. 위에서 $i$ 행째, 왼쪽에서 $j$ 번째의 매스눈을 매스 $(i,j)$ 라고 부르기로 한다.

현재 각 칸은 장애물이 있거나 비어있는 상태입니다. 이러한 상태는 $S_1,S_2,\cdots,S_N$ 문자열로 표시되며, 매스 $(i,j)$ 의 상태는 $S_{i,j}=$ '#' 가 놓여 있는 것, $S_{i,j}=$ '.' 그렇다면 비어 있음을 의미합니다.

이 매스에 $1\times2$ 크기의 타일을 넣고 싶습니다. 타일은 세로 또는 가로로 연속하는 $ 2 $의 빈 매스 위에 놓을 수 있습니다. 타일을 반면에서 돌출시키거나 장애물이나 다른 타일이 이미 놓여져 있는 매스에 타일을 겹치는 것은 금지되어 있습니다. 최대 몇 개의 타일을 넣을 수 있는지 묻습니다. 또한 실제로 최대 값을 달성하는 방법을 $ 1 $ 보여줍니다.

제약

$1\le N\le 100$

$1\le M\le 100$

해설

매스를 우기로 나누어 생각합니다. 각각의 빈 매스 $(i,j)$ 에 대해, $i+j$ 가 짝수가 되는 매스를 검정, 홀수가 되는 매스를 흰색으로 바르기로 하면, 체크 무늬가 됩니다.

여기에 $1\times2$ 의 크기의 타일을 두는 것은, 블랙 매스와 화이트 매스를 연결하는 것으로 생각할 수 있습니다.

그러면 이것은 검은 송어와 흰 송어의 쌍을 만들 때 최대 몇 쌍을 만들 수 있는지 문제가됩니다. 즉 최대 2부 매칭 문제가 되어, maxflow를 사용해 해결할 수 있습니다.

1. 블랙 매스와 화이트 매스를 각각 정점으로 하고, 한층 더 소스와 싱크의 2개의 정점을 추가합니다.
2. 소스에서 모든 검은 송어로의 변과, 검은 송어에서 인접한 흰 송어로의 면과, 모든 흰 송어에서 싱크로의 면을 붙입니다. 가장자리의 용량은 모두 $1$입니다.
3. 소스에서 싱크까지의 최대 유량을 찾습니다. 이것이 둘 수 있는 타일의 개수입니다.

게다가 이 때의 각변의 플로우를 얻을 필요가 있습니다만, 이것은 ACL 라고 '#' 그리고 할 수 있으므로, 좋게.