[BZOJ2756][SCOI2012]奇怪的游戏(二分,网络流)

发布于 16 天前  17 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2756][SCOI2012]奇怪的游戏(二分,网络流)

Description

Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻的格子,并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同一个数则输出-1。

Tag

二分,网络流

解决思路

将格子黑白染色后,统计黑白格子的数量和分别的和。设数量分别为\(cnt1,cnt2\),和分别为\(sum1,sum2\),然后讨论。
对于黑白格子数量一样的,当\(sum1!=sum2\)时,一定无解,因为观察题目中的操作可以发现,每一次操作一定是给一个白色格子和一个黑色格子分别+1,而当黑色与白色格子一样时,若和不一样,则永远都不会一样,永远无解;当\(sum1==sum2\)时,一定有解,并且对于合法的答案\(X\),\(X+1\)一定有解,那么可以二分这个答案,然后判定是否合法。
对于黑白格子数量不一样的,此时可以直接得出最后全部应该变成的数。设这个数为X,则一定有
X*cnt1-sum1==X*cnt2-sum2

那么移项既可以得到X的值,判断是否合法即可。
至于如何判断一个最终数X的合法性,建立源点和汇点,源点连向黑格,黑格连向相邻的白格,白格连向汇点,黑白格之间流量为无穷,而分别与源汇点的流量为原数值减去X。当满流即合法。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2756][SCOI2012]奇怪的游戏(二分,网络流)


HNCJ OIer 一枚