To_Heart—题解——[SCOI2012]奇怪的游戏

题意

link.

给定一个 $n\times m$ 的棋盘，每次操作可以选择两个相邻的格子，让这两个各自上的数都 +1。问最少多少次操作使得所有格子的数相等。如果永远不行则输出-1。

题解

因为相邻两个格子进行操作，而且是方格，所以很容易想到黑白染色（好久没做题了这个都想不到了/kk）。

黑白染色后发现如果黑色格子数量等于白色格子数量，那我们可以转换成二分图网络流模型，这部分应该是个很常见的 trick，二分一下操作次数判断是否满流，然后无解的判断在于一开始黑白两种格子的权值和是否相等。

但是但是如果黑色格子数量与白色不相等呢？这时候其实可以直接确定最后的每个格子的值。

假设白色格子有 $w$ 个，权值和为 $W$；黑色格子有 $b$ 个，权值和为 $B$。再假设最后每个格子的权值为 $x$，那么有：

$$w\times x-W=b\times x-B$$

因为次数是相等的。转换一下得到：

$$x=\frac{B-W}{b-w}$$

然后因为 $b\ne w$，所以这个 $x$ 可以直接解出来。

那么我们直接用二分图那个来判断一下是否有解就行了。