FoxAndGo3

作者：寇煜杭

关键字：最小割 网络流

题目简述

给你一个$n*n$的网格。每个格子只会存在这三种$x$(黑块),$o$(白块),$.$(空格).现在你要向空格上放黑块，对于任意一个白块上下左右如果全是黑块，那么这个白块就会变成空格。现在求空格最大能达到多少个？(保证没有任意两个白块相邻，任意白块上下左右必有一个空格，$n<=50$).

解题思路

可以发现这是一道最小割问题。将空格和白块看做点并进行标号。把每一个空格向它上下左右的白块建一条容量为$1$的边,由一个超级源向所有空格连一条容量为$1$的边,所有的白块向超级汇连一条容量为$1$的边。跑一遍网络流，最终答案为空格和白块的数量总和减去最大流量。

时间复杂度$O(n^4*m)$.($m$最大为$3*n$).