[SCOI2012]奇怪的游戏

题目

Description

Blinker最近喜欢上一个奇怪的游戏。这个游戏在一个N*M的棋盘上玩，每个格子有一个数。

每次Blinker会选择两个相邻的格子，并使这两个数都加上 1。

现在Blinker想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。

Input

输入的第一行是一个整数T，表示输入数据有T轮游戏组成。

每轮游戏的第一行有两个整数N和M，分别代表棋盘的行数和列数。

接下来有N行，每行M个数。

Output

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

Sample Input

Sample Output

2
-1

HINT

【数据范围】

对于30%的数据，保证T<=10，1<=N,M<=8

对于100%的数据，保证T<=10，1<=N,M<=40，所有数为正整数且小于1000000000

题解

由于每次选择的两个格子都是相邻的，所以我们考虑黑白染色

设黑格子里的数的总和为$sum0$，白格子里的数的总和为$sum1$，黑格子有$tot0$个，白格子有$tot1$个

分类讨论：

若$sum0!=sum1$

假设最后每个格子里的数都是$ans$

则有$ans\times sum0-tot0=ans\times sum1-tot1$

即$ans=\frac {tot0-tot1}{sum0-sum1}$

然而我们还需要检验一下$ans$的正确性（如果不可能所有格子一样$ans$的假设不成立）

首先一定有$max\leq ans$(原先格子值)~~不然你怎么操作~~

考虑网络流，源点向黑格子连边，容量为$ans$-原先格子的值（补成$ans$需要加多少），白格子向汇点连边，容量也为$ans$-原先格子的值

然后每个黑格子向ta相邻的白格子连边，容量为$inf$

如果最大流的答案$=ans\times sum0-tot0$，说明成立

若$sum0=sum1$

这就相当于拿$1\times 2$大小的方块覆盖原图使原图各处高度一样

如果$ans$存在，$ans+1$肯定满足条件（在高度都为$ans$的基础上再覆盖一层）

考虑二分答案，每次用网络流判断

注意答案不是$ans$，而是$ans\times sum0-tot0$，并且有些地方爆int了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
# define pu(x,y) (x-1)*m+y
# define LL long long
using namespace std;
const int MAX=1e5+1,t=1e5;
const LL inf=1e15;
struct p{
	int x,y;
	LL dis;
}c[MAX<<2];
int n,m,num=2,T;
LL sum1,sum0,tot1,tot0;
int h[MAX],d[MAX];
LL b[41][41];
int mv1[4]={0,0,1,-1};
int mv2[4]={1,-1,0,0};
LL read()
{
	LL x=0,f=1;
	char ch=getchar();
	for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x*f;
}
void add(int x,int y,LL dis)
{
	c[num]=(p){h[y],x,0},h[y]=num++;
	c[num]=(p){h[x],y,dis},h[x]=num++;
}
bool bfs()
{
	queue<int> qu;
	qu.push(0);
	memset(d,0,sizeof(d));
	d[0]=1;
	while(!qu.empty())
	{
		int tt=qu.front();
		qu.pop();
		for(int i=h[tt];i;i=c[i].x)
		  if(!d[c[i].y]&&c[i].dis)
		  {
		  	d[c[i].y]=d[tt]+1;
		  	qu.push(c[i].y);
		  }
	}
	return d[t];
}
LL dfs(int x,LL dix)
{
	if(x==t||!dix) return dix;
	LL sum=0;
	for(int i=h[x];i;i=c[i].x)
	  if(d[c[i].y]==d[x]+1&&c[i].dis)
	  {
	  	LL dis=dfs(c[i].y,min(c[i].dis,dix));
	  	if(dis)
	  	{
	  		sum+=dis;
	  		dix-=dis;
	  		c[i].dis-=dis;
	  		c[i^1].dis+=dis;
	  		if(!dix) break;
		}
	  }
	if(!sum) d[x]=-1;
	return sum;
}
LL dinic()
{
	LL tot=0;
	while(bfs()) tot+=dfs(0,inf);
	return tot;
}
bool look(LL mid)
{
	memset(c,0,sizeof(c));
	memset(h,0,sizeof(h));
	num=2;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    if(!((i+j)%2))
	    {
	    	add(0,pu(i,j),mid-b[i][j]);
	    	for(int k=0;k<=3;k++)
	    	  {
	    	  	int xx=i+mv1[k],yy=j+mv2[k];
	    	  	if(xx<1||xx>n||yy<1||yy>m) continue;
	    	  	add(pu(i,j),pu(xx,yy),inf);
			  }
		}
	    else add(pu(i,j),t,mid-b[i][j]);
	if(dinic()==mid*sum0-tot0) return 1;
	return 0;
}
int main()
{
	T=read();
	while(T--)
	{
		sum0=0,sum1=0,tot0=0,tot1=0;
		LL maxn=0;
		n=read(),m=read();
		for(int i=1;i<=n;i++)
		  for(int j=1;j<=m;j++)
		    {
		    	b[i][j]=read();
		    	maxn=max(maxn,b[i][j]);
		    	if(!((i+j)%2)) sum0++,tot0+=b[i][j];
		    	else sum1++,tot1+=b[i][j];
			}
		if(sum0!=sum1)
		{
			LL ans=(tot0-tot1)/(sum0-sum1);
			if(ans>=maxn&&look(ans)) printf("%lld\n",ans*sum0-tot0);
			else printf("-1\n");
			continue;
		}
		LL l=maxn,r=inf,ans=-1;
		while(l<=r)
		{
			LL mid=(l+r>>1);
			if(look(mid)) r=mid-1,ans=mid;
			else l=mid+1;
		}
		if(ans!=-1) printf("%lld\n",ans*sum0-tot0);
		else printf("-1\n");
	}
	return 0;
}

题目