「BZOJ2756」[SCOI2012]奇怪的游戏

Description

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

Input

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

Output

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

Sample Input

1
2
3
4
5
6
7
8
2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2

Sample Output

1
2
2 
-1

HINT

对于30%30\%的数据,保证 T10T\leq 101N1\leq N,M8M\leq 8
对于100%100\%的数据,保证 T10T\leq 101N,M401\leq N,M\leq 40,所有数为正整数且小于10000000001000000000

Solution

假设最后每个格子都等于xx
给格子按照i+ji+j的奇偶性分成黑点和白点。
n0n_0表示白点个数,s0s_0表示所有白点的值之和。
根据题意有n0xs0=n1xs1x=s0s1n0n1n_0x-s_0=n_1x-s_1\Rightarrow x=\frac{s_0-s_1}{n_0-n_1}。也就是黑点和白点总共加的值相等。

  1. n0n1n_0\neq n_1,那么xx可以直接求出来,用checkcheck函数一下。
  2. n0=n1n_0= n_1,那么对于任意的xx都是可行的,所以我们要枚举xx,同时xx具有二分的性质,也就是xx如果可以,那么x\leq x的都可以,因为可以整体加上vv。如果xx不可以,那么<x< x的都不可以。

checkcheck:

  • ss分别连向所有黑点一条容量为xai,jx-a_{i,j}的边
  • 从所有白点分别连tt一条容量为xai,jx-a_{i,j}的边
  • 对所有的黑点遍历四周,向白点连容量为infinf的边
    跑一遍最大流,若ss流出的量和流入tt的流量相等,那么合法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#include<queue>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 50;
int n, m;
struct Edge {
int u, v, nxt;
ll f;
}e[N * N * 2*8];
int head[N * N], en = 1;
void addedge(int x, int y, ll z) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0;
}
int a[N][N];
int s, t;
int id(int x, int y) {
return (x - 1) * m + y;
}
const ll inf = 1e17;

int d[N * N];
bool bfs() {
queue<int>q;
for(int i = 1;i<=t;++i) d[i]=0;
d[s] = 1;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f) {
int y = e[i].v;
if(!d[y]) {
d[y] = d[x] + 1;
if(y == t) return 1;
q.push(y);
}
}
}
return 0;
}
ll dinic(int x, ll flow) {
if(x==t)return flow;
ll k, rest = flow;
for(int i = head[x]; rest && i; i = e[i].nxt) if(e[i].f && d[e[i].v] == d[x] + 1) {
int y = e[i].v;
k = dinic(y, min(rest, e[i].f));
e[i].f -= k;
e[i ^ 1].f += k;
rest -= k;
}
if(rest == flow) d[x] = 0;
return flow - rest;
}
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool check(ll x) {
s = n * m + 1;
t = n * m + 2;
memset(head,0,sizeof head);
en = 1;
ll res = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(x < a[i][j]) return 0;
if((i + j) & 1) {
addedge(id(i, j), t, x - a[i][j]);
res += x - a[i][j];
} else {
addedge(s, id(i, j), x - a[i][j]);
for(int k = 0; k < 4; ++k) {
int nx = i + dx[k], ny = j + dy[k];
if(nx <1 || ny <1||nx>n||ny>m)continue;
addedge(id(i,j),id(nx,ny),inf);
}
}
}
}
ll flow = 0, y;
while(bfs())
while(y = dinic(s, inf)) flow += y;
return flow == res;
}

int main() {
int T = read();
while(T--) {
n = read(), m = read();
ll c[2] = {0};
ll t[2] = {0};

for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) a[i][j] = read(), c[(i + j) & 1] += a[i][j], ++t[(i+j)&1];
if(!(n & 1) || !(m & 1)) {
ll l = 0, r = 1e16;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid;
}
if(check(r)) writeln(r * t[0] - c[0]);
else puts("-1");
} else {
if(c[0] < c[1]) swap(c[0], c[1]), swap(t[1], t[0]);
ll x = (c[0] - c[1]) / (t[0] - t[1]);
if(x >= 0 && check(x)) writeln(x * t[0] - c[0]);
else writeln(-1);
}
}
return 0;
}