首页 > 代码库 > BZOJ 2756: [SCOI2012]奇怪的游戏
BZOJ 2756: [SCOI2012]奇怪的游戏
2756: [SCOI2012]奇怪的游戏
Time Limit: 40 Sec Memory Limit: 128 MBSubmit: 3410 Solved: 941
[Submit][Status][Discuss]
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
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2
Sample Output
2
-1
-1
HINT
【数据范围】
对于30%的数据，保证 T<=10，1<=N,M<=8
对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000
Source
二分答案 + 网络流判断
不难看出，对棋盘进行黑白染色之后，每次相加都会使得相邻的一黑一白两个格子同时+1,。
先对所有黑白格子进行统计，处理出$cnt0$,$cnt1$分别代表黑、白格子个数，处理出$sum0$,$sum1$分别代表黑、白格子权值和。
分类讨论如下：
如果$cnt0=cnt1$
如果$sum0\not = sum1$
BZOJ 2756: [SCOI2012]奇怪的游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。