BZOJ 2756 [SCOI2012] 奇怪的游戏

发布于 2017-08-19  142 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2756

题意: N*M 的棋盘每个格子有一个数。每次选择两个相邻的格子加 1。 最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同一个数则输出-1。


黑白染色,选择两个相连的格子就是选择一个黑格子一个白格子。

设黑格子总数\(cnt_{1}\) 个,白格子总数\(cnt_{2}\) 个,黑格子权值和\(sum_1\),白格子权值和\(sum_2\),变成的那个数为 x。

那么可以列出这么个式子...\(x=\frac{sum_1-sum_2}{cnt_1-cnt_2}\)

诶?解出 x,判断是否合法好像就做完了? 然而没有,因为可能存在\(cnt_1=cnt_2\) 的情况

这种情况下,若\(sum_1!=sum_2\) 则必定无解,否则考虑若 ans 合法,则 ans+1 必然合法,因为相当于都加一遍。所以满足二分性质。

二分答案再判断答案是否合法即可了。

于是现在的瓶颈在于如何判断一个答案是否合法... 网络流这样建模:

S-> 黑格子 x-a[i][j]

白格子->T x-a[i][j]

黑格子-> 相邻白格子 inf

于是就结束了 T.T T 个不停原来是因为数组开小...

 

 


一个非常弱的准退役OIER