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
Source
cxjyxx_me:
Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻
的格子，并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同
一个数则输出-1。
对棋盘进行黑白染***r> 设黑格个数为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)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define M 20005
#define inf (1LL<<50)
#define pa pair<int,int>
#define ll long long
#define p(x,y) (x-1)*m+y
using namespace std;
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch-'0'; ch = getchar(); }
return x * f;
}
ll s0,s1;
int c0,c1;
int test,n,m,cnt,S,T;
int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
int a[45][45];
int head[2005],h[2005],q[2005],cur[2005];
bool color[45][45];
struct edge
{
int to, next;
ll v;
}e[20005];
void ins(int u, int v, ll w)
{
e[++ cnt].next = head[u];
head[u] = cnt;
e[cnt].to = v;
e[cnt].v = w;
}
void insert(int u, int v, ll w)
{
ins(u, v, w);
ins(v, u, 0);
}
ll dfs(int x, ll f)
{
if(x == T) return f;
ll used = 0, w;
for(int i = head[x]; i; i = e[i].next)
{
int y = e[i].to;
if(h[y] == h[x] + 1 && e[i].v)
{
w = dfs(y, min(e[i].v, f - used));
e[i].v -= w;
if(e[i].v) cur[x] = i;
e[i^1].v += w;
used += w;
if(f == used) return f;
}
}
if(used == 0) h[x] = -1;
return used;
}
int bfs()
{
int t = 0, w = 1;
memset(h, -1, sizeof(h));
q[0] = S;
h[S] = 0;
while(t != w)
{
int now = q[t ++];
if(t == M) t = 0;
for(int i = head[now]; i; i = e[i].next)
{
int y = e[i].to;
if(h[y] == -1 && e[i].v)
{
h[y] = h[now] + 1;
q[w ++] = y;
if(w == M) w = 0;
}
}
}
if(h[T] == -1) return 0;
else return 1;
}
ll dinic()
{
ll ans = 0ll;
while(bfs())
{
for(int i = S; i <= T; i ++)
cur[i] = head[i];
ans += dfs(S, inf);
}
return ans;
}
bool check(ll x)
{
memset(head,0,sizeof(head));
cnt = 1;
S = 0;
T = n * m + 1;
ll tot = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
if(color[i][j])
{
insert(S, p(i,j), x - a[i][j]);
tot += x - a[i][j];
for(int k = 0; k < 4; k ++)
{
int nowx = i + xx[k], nowy = j + yy[k];
if(nowx < 1 || nowy < 1 || nowx > n || nowy > m)continue;
insert(p(i, j),
p(nowx, nowy), inf);
}
}
else insert(p(i, j), T, x - a[i][j]);
if(dinic() == tot)return 1;
return 0;
}
int main()
{
test = read();
while(test --)
{
c0 = c1 = s0 = s1 = 0;
n = read();
m = read();
int mx = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
a[i][j] = read(), color[i][j] = (i + j) & 1;
mx = max(mx, a[i][j]);
}
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
if(color[i][j]) s1 += a[i][j], c1 ++;
else s0 += a[i][j], c0 ++;
if(c0 != c1)
{
ll x = (s0 - s1) / (c0 - c1);
if(x >= mx)
if(check(x))
{
printf("%lld\n",x * c1 - s1);
continue;
}
puts("-1");
}
else
{
ll l = mx, r = inf;
while(l <= r)
{
ll mid = (l + r) >> 1;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
printf("%lld\n",(ll)l * c1 - s1);
}
}
return 0;
}
京公网安备 11010502036488号