公式化网络流的套路。把变量设对了就会做了。

首先有两个显然的观察：

1. 如果确定了操作集合，执行操作的顺序肯定是先做所有长条黑操作，再做所有长条白操作，最后做所有单点操作。
2. 两个行操作不会相交。

然后设 表示 格子有没有被横向黑、纵向黑、横向白、纵向白染过。染过为 否则为 。

那横向黑操作的总代价就是 。

如果一个点最后要求是黑色，其还会提供 的代价。

如果要求是白色，会提供 的代价。

当有 个取值 的变量，且最后代价形如 时，我们有如下最优化方法：

建立 个点的图 ，用 到 的最小割来表述 的取值。如果在最小割中 与 在同一集合则说明 ，否则说明 ，那么对于代价中的一项 ，从 向 连一条边权为 的边。对于一项 ，由 向 连一条边权为 的边，表示要让 与 在一起需要将这条边割掉，耗费 代价。

但这道题中的代价有形如 的项。我们考虑做一些处理，将 和 反转一下，如果没有被对应操作染过则值为 ，否则值为 。那么代价式子中的每一项就都是 的形式，用上述办法最优化即可。