【bzoj2756】[SCOI2012]奇怪的游戏

2015年1月3日3,8226

Description

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

Input

输入的第一行是一个整数T,表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M, 分别代表棋盘的行数和列数。
接下来有N行,每行 M个数。

Output

  对于每个游戏输出最少能使游戏结束的次数,如果永远不能变成同一个数则输出-1。

Sample Input

2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2

Sample Output

2
-1

HINT

【数据范围】
对于30%的数据,保证  T<=10,1<=N,M<=8
对于100%的数据,保证  T<=10,1<=N,M<=40,所有数为正整数且小于1000000000

题解

对棋盘进行黑白染色
设黑格个数为num1 数值和为sum1
设白格个数为num1 数值和为sum1

设最后都变为x

num1 * x – sum1 = num2 * x – sum2
x = (sum1 – sum2) / (num1 – num2)
当num1 ≠ num2时 可以解出 x 再用网络流check即可

对于num1 = num2时 可以发现 对于一个合法的x k>=x都是一个合法的解
因为num1 = num2 => (num1 + num2) % 2 == 0 可以构造一层的满覆盖
所以可以二分x 然后用网络流check

建图:
如果点k为白
建边(s, k, x – v[k])
如果为黑
建边(k, t, x – v[k])
对相邻点u、v (u为白)
建边 (u, v, inf)

 

  • 伪日常系LordNanoApe2015年6月15日 下午7:02 回复

    程序有错误,测试数据如下:
    1
    2 3
    0 4 0
    3 6 6
    正确答案应该是-1

    #1  
  • ...2015年11月19日 下午11:08 回复

    应该还有当 c0=c1,如果s0!=s1,输出-1

    #2  
    • hzwer2016年7月12日 下午9:10 回复
      admin

      已改

      #21
      • cgh2016年7月13日 上午8:41 回复

        黄学长 不是return 0 啊 是continue吧?

        #22
        • hzwer2016年7月13日 上午10:51 回复

          QAQ

          #23
          • cgh2016年7月14日 上午9:38

            这个也是黄学长的号吗、、

            #24