题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2756
Description
Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻的格子，并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。
Input
输入的第一行是一个整数T，表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M， 分别代表棋盘的行数和列数。
接下来有N行，每行 M个数。
Output
对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。
Sample Input
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2
Sample Output
-1
HINT
【数据范围】
对于30%的数据，保证 T<=10，1<=N,M<=8
对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000
——————————————————————————————————————————————————
题意概述：
给出一个N*M的棋盘，每个格子有一个数，每次可以选择两个相邻的格子都+1。
问最少操作多少次可以让所有的数变得一样，如果无解输出-1。
分析：
发现只知道操作次数并没有什么用（因为你也不知道要怎么去填）。
假设最后的格子里的数是x。
每次操作对相邻的两个格子进行，发现可以把棋盘上的格子分开来，黑白染色。
抽象化表达：
假设有c1个白色格子，c2个黑色格子，一开始白色格子的和为s1，黑色格子的和为s2，那么假如答案可以成立，由分别对于黑白格子操作次数相同，有：
c1*x-s1=c2*x-s2 -> (c1-c2)*x=s1-s2
可以发现当c1=c2的时候x的值并不是唯一确定的，但是根据黑白染色的分析，可以发现这种情况下棋盘长宽中至少有一个是偶数，黑白可以两两配对，满足二分性质。
问题转化为判定。
建立源点S，汇点T，S向所有的白格子连边，容量为需要提升的值，黑格子向T连边，容量也为需要提升的值。
白点向周围的黑点连边，意义为这两个点一起提升的值，容量为inf。跑最大流看是否满流即可。
c1-c2!=0 -> x=(s1-s2)/(c1-c2)，那么可以直接判定：是否大于等于最大格子，是否可以整除，是否可以判定成功。
小结：性质分析不出来怎么办？抽象成数学表达式再分析aaaaaaa！！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
#define inf (1e12+5)
using namespace std;
const int MAXN=;
typedef long long LL; int T,N,M,A[MAXN][MAXN];
int c1,c2,MAX; LL s1,s2;
struct NET{
static const int maxn=;
static const int maxm=;
struct edge{ int from,to,next; LL cap,flow; }E[maxm];
int n,S,T,first[maxn],np,d[maxn],gap[maxn],fl[maxn],cur[maxn];
NET(){ np=; }
void add_edge(int u,int v,LL c){
E[++np]=(edge){u,v,first[u],c,};
first[u]=np;
E[++np]=(edge){v,u,first[v],,};
first[v]=np;
}
int id(int x,int y){ return (x-)*M+y; }
void init(LL m){
memset(first,,sizeof(first));
np=,n=N*M+,S=n-,T=n;
LL re=;
for(int i=;i<=N;i++)
for(int j=;j<=M;j++){
if((i&)&&(j&)||!(i&)&&!(j&)){
add_edge(S,id(i,j),m-A[i][j]);
if(i-) add_edge(id(i,j),id(i-,j),inf);
if(j-) add_edge(id(i,j),id(i,j-),inf);
if(i+<=N) add_edge(id(i,j),id(i+,j),inf);
if(j+<=M) add_edge(id(i,j),id(i,j+),inf);
}
else add_edge(id(i,j),T,m-A[i][j]);
}
}
void BFS(){
queue<int>q;
for(int i=;i<=n;i++) d[i]=n;
d[T]=; q.push(T);
while(!q.empty()){
int i=q.front(); q.pop();
for(int p=first[i];p;p=E[p].next){
int j=E[p].to,pp=(p-^)+;
if(d[j]==n&&E[pp].cap>E[pp].flow) d[j]=d[i]+,q.push(j);
}
}
}
LL augment(){
LL flow=inf; int now=T;
while(now!=S){
flow=min(flow,E[fl[now]].cap-E[fl[now]].flow);
now=E[fl[now]].from;
}
now=T;
while(now!=S){
E[fl[now]].flow+=flow,E[(fl[now]-^)+].flow-=flow;
now=E[fl[now]].from;
}
return flow;
}
bool ISAP(){
memcpy(cur,first,sizeof(first));
memset(gap,,sizeof(gap));
BFS();
for(int i=;i<=n;i++) gap[d[i]]++;
int now=S; LL flow=;
while(d[S]<n){
if(now==T) flow+=augment(),now=S;
bool ok=;
for(int p=cur[now];p;p=E[p].next){
int j=E[p].to;
if(E[p].cap>E[p].flow&&d[j]+==d[now]){
ok=,cur[now]=fl[j]=p,now=j;
break;
}
}
if(!ok){
int minl=n;
for(int p=first[now];p;p=E[p].next){
int j=E[p].to;
if(E[p].cap>E[p].flow&&d[j]+<minl) minl=d[j]+;
}
if(--gap[d[now]]==) break;
gap[d[now]=minl]++;
cur[now]=first[now];
if(now!=S) now=E[fl[now]].from;
}
}
for(int p=first[S];p;p=E[p].next)
if(E[p].cap!=E[p].flow) return ;
for(int p=first[T],pp=(p-^)+;p;p=E[p].next,pp=(p-^)+)
if(E[pp].cap!=E[pp].flow) return ;
return ;
}
}net; void data_in()
{
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++)
for(int j=;j<=M;j++)
scanf("%d",&A[i][j]);
c1=c2=MAX=,s1=s2=;
for(int i=;i<=N;i++)
for(int j=;j<=M;j++){
if((i&)&&(j&)||!(i&)&&!(j&)) s1+=A[i][j],c1++;
else s2+=A[i][j],c2++;
MAX=max(MAX,A[i][j]);
}
}
bool check(LL mid)
{
net.init(mid);
return net.ISAP();
}
void work()
{
if(c1==c2){
LL L=MAX,R=inf,mid,ans=-;
while(L<R){
mid=L+R>>;
if(check(mid)) R=mid,ans=mid;
else L=mid+;
}
if(ans!=-) cout<<(ans*N*M-s1-s2)/<<'\n';
else cout<<ans<<'\n';
}
else{
if((s1-s2)%(c1-c2)==&&(s1-s2)/(c1-c2)>=MAX){
LL ans=(s1-s2)/(c1-c2);
if(check(ans)) cout<<(ans*N*M-s1-s2)/<<'\n';
else cout<<-<<'\n';
}
else cout<<-<<'\n';
}
}
int main()
{
scanf("%d",&T);
while(T--){
data_in();
work();
}
return ;
}