题意#
给一个 $n \times m$ 的棋盘，每个位置有空、黑、白三种情况。现在需要填充空的位置，使得颜色不同的、行坐标差为 $a$、列坐标差为 $b$ 的棋子对数尽可能多。但要给出字典序最小的解。
题解#
如果是数颜色相同，也不给方案，就简单的多。每个位置可以看作网络流上的一个点。如果和 S 划在一起，则认为这个位置放黑棋子，和汇点划一起则放白棋子。坐标距离满足限制的两个点互相连一个容量为 1 的边，如果两个位置颜色不同则会割到这条边。
但现在是颜色不同，需要换一下意义。
容易发现满足坐标距离限制的点可以黑白染色（下文改称红蓝），每 $a$ 行一组，红蓝交替染色（前 $a$ 行染红，接下来 $a$ 行染蓝……）。
红点若和 S 划一起，则认为这个位置放黑的；蓝点若和 S 划一起，则认为放白的；反过来相对应的红 T 染白，蓝 T 染黑。
这样连边和上面颜色相同时候的情况也是一样的，距离满足限制的互相连容量为 1 的边，这样连接的肯定分别是红蓝两点。
强制让某个点为黑或白棋子，则按上面的红蓝点和源汇的关系连一个无穷大的边即可。
答案即为距离满足限制的点对数量，减 S-T 最小割的值。
方案#
方案是个麻烦东西，还要字典序最小。
从上到下、从左到右，贪心看这个点能不能染黑的。
在残余网络上，从源点出发染色、从汇点出发反向染色，若这个点在残余网络上和源点相连，则说明必然把它和 S 割在了一起；反之和 T 割在一起。
对于没有染到的点，那这个点可以是黑的。此时已知该点为黑色的，潜在地需要再根据上面的所说的和源或汇连边，跑网络流，并再进行染色。但这不必要，因为答案已经不会改变，所以可以直接假装这个点和源或汇有边，在之前染色的基础上再染色。
类似于已知某个点是黑棋子，然后根据已知情况去递归放空位置的黑白棋子，以避免后续错放成黑的。
评论