To_Heart—题解——[SCOI2012]奇怪的游戏
题意
link.
给定一个 n×mn\times mn×m 的棋盘，每次操作可以选择两个相邻的格子，让这两个各自上的数都 +1。问最少多少次操作使得所有格子的数相等。如果永远不行则输出-1。
题解
因为相邻两个格子进行操作，而且是方格，所以很容易想到黑白染色（好久没做题了这个都想不到了/kk）。
黑白染色后发现如果黑色格子数量等于白色格子数量，那我们可以转换成二分图网络流模型，这部分应该是个很常见的 trick，二分一下操作次数判断是否满流，然后无解的判断在于一开始黑白两种格子的权值和是否相等。
但是但是如果黑色格子数量与白色不相等呢？这时候其实可以直接确定最后的每个格子的值。
假设白色格子有 www 个，权值和为 WWW；黑色格子有 bbb 个，权值和为 BBB。再假设最后每个格子的权值为 xxx，那么有：
w×x−W=b×x−Bw\times x-W=b\times x-Bw×x−W=b×x−B
因为次数是相等的。转换一下得到：
x=B−Wb−wx=\frac{B-W}{b-w}x=b−wB−W
然后因为 b≠wb\neq wb=w，所以这个 xxx 可以直接解出来。
那么我们直接用二分图那个来判断一下是否有解就行了。