标签：网络流，最大流
题目
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
分析
将棋盘进行黑白点染色，设黑点个数为c1，总和为$ s1=\sum a[i][j] $
白点个数为c2，总和为 $ s2=\sum a[i][j] $
设最后所有的格子内都变成x
那么列出方程
$ c1x-s1=c2x-s2 $
$ x=(s1-s2)/(c1-c2) $
解出x之后可以用网络流检验答案是否可行
建图过程：
将超级源点S=0向每个黑点连边流量为x-a[i][j]，黑点和白点之间连边流量为无穷大，白点再和超级汇点连边流量为x-a[i][j]
最后看总的流量是不是$ \sum x-a[i][j] $
如果符合条件那么输出答案x，否则输出-1
但是当c1=c2时，就无法解得x，显然存在一个最小值x，满足k>=x都是一个合法的解
那么可以二分答案x（每点最终权值）然后同样用最大流dinic解决
这题调试了大半天，原因竟是数组开小，可是神奇的bzoj提醒我TLE，明明实际上是RE啊，bzoj=玄学OJ，有没有大佬知道原因的啊qwq
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define inf 1LL<<50
#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;
}
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll s1,s2,ans;
int c1,c2,S,T,n,m,cnt,Que,last[2006],h[2006],que[2006],a[46][46];
bool col[46][46];
struct edge{int to,next;ll v;}e[20006];
void insert(int u,int v,ll w){
e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}
bool bfs()
{
int head=0,tail=1,now;
mem(h,-1);
que[0]=S;h[S]=0;
while(head<tail){
now=que[head++];
reg(now)
if(e[i].v&&h[e[i].to]==-1){
h[e[i].to]=h[now]+1;
que[tail++]=e[i].to;
}
}
return h[T]!=-1;
}
inline ll dfs(int x,ll f)
{
if(x==T)return f;
ll w,used=0;
reg(x)
if(h[e[i].to]==h[x]+1){
w=dfs(e[i].to,min(f-used,e[i].v));
e[i].v-=w;e[i^1].v+=w;
used+=w;if(used==f)return f;
}
if(!used)h[x]=-1;
return used;
}
inline ll dinic(){
ll temp=0;
while(bfs())temp+=dfs(S,inf);
return temp;
}
bool check(ll x)
{
mem(last,0);mem(e,0);
cnt=1;S=0;T=n*m+1;
ll tot=0;
rep(i,1,n)
rep(j,1,m)
if(col[i][j]){
insert(S,p(i,j),x-a[i][j]);tot+=x-a[i][j];
rep(k,0,3){
int nx=i+dx[k],ny=j+dy[k];
if(nx<1||nx>n||ny<1||ny>m)continue;
insert(p(i,j),p(nx,ny),inf);
}
}
else insert(p(i,j),T,x-a[i][j]);
if(dinic()==tot)return 1;else return 0;
}
int main()
{
Que=read();
while(Que--){
int Max=0;
n=read(),m=read();
c1=c2=s1=s2=0;
rep(i,1,n)
rep(j,1,m){
a[i][j]=read();
col[i][j]=(i+j)&1;Max=max(Max,a[i][j]);
}
rep(i,1,n)
rep(j,1,m)
if(col[i][j])s2+=a[i][j],c2++;
else s1+=a[i][j],c1++;
if(c1!=c2){
ll x=(s1-s2)/(c1-c2);
if(x>=Max)
if(check(x)){printf("%lld\n",(ll)x*c2-s2);continue;}
puts("-1");
}
else{
if(s1!=s2){puts("-1");continue;}
ll l=Max,r=inf;
while(l<=r){
ll mid=(l+r)/2;
if(check(mid))r=mid-1;else l=mid+1;
}
printf("%lld\n",(ll)l*c2-s2);
}
}
return 0;
}
