bzoj2756: [SCOI2012]奇怪的游戏

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2756

思路：先黑白染色，设白格个数为cnt0，和为sum0，黑格个数为cnt1，和为sum1，假设最后所有点都变成了x

那么如果cnt0!=cnt1就是格子数为奇数时

cnt0*x-sum0=cnt1*x-sum1

x=(sum0-sum1)/(cnt0-cnt1)

格子为偶数时x没有意义

我们就要想新的方法

格子为偶数，那么如果x合法，那么x+1也会合法

这个可以构造证明，两两配对+1即可

所以这种情况可以二分

知道x后就可以用网络流check了

S向白格连x-num[i][j]的边

白点向相邻黑点连inf的边，

黑点向T连x-num[i][j]的边即可

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
const int maxn=1610,maxm=20010;
const ll inf=1ll<<50;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
using namespace std;
int cas,n,m,S=maxn-2,T=maxn-1,cnt0,cnt1;
int pre[maxm],now[maxn],son[maxm],tot,q[maxn+10],head,tail,dis[maxn];
ll sum0,sum1,X,val[maxm],num[45][45],maxs;
void add(int a,int b,ll c){pre[++tot]=now[a],now[a]=tot,son[tot]=b,val[tot]=c;}
void ins(int a,int b,ll c){add(a,b,c),add(b,a,0);}//,printf("%d %d %lld
",a,b,c);
//0是白，即x+y为偶数的格子,1是黑
int id(int x,int y){return (x-1)*m+y;}
void init(){
	scanf("%d%d",&n,&m),maxs=sum0=cnt0=sum1=cnt1=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			scanf("%lld",&num[i][j]),maxs=max(maxs,num[i][j]);
			if (!((i+j)&1)) sum0+=num[i][j],cnt0++;
			else sum1+=num[i][j],cnt1++;
		}
}

bool bfs(){
	memset(dis,-1,sizeof(dis));
	q[tail=1]=S,dis[S]=head=0;
	while (head!=tail){
		if (++head>maxm) head=1;
		int x=q[head];
		for (int y=now[x];y;y=pre[y]) if (val[y]&&dis[son[y]]==-1){
			if (++tail>maxm) tail=1;
			q[tail]=son[y],dis[son[y]]=dis[x]+1;
		}
	}
	return dis[T]>0;
}

ll find(int x,ll low){
	if (x==T) return low;
	int y;ll res=0;
	for (y=now[x];y;y=pre[y]){
		if (dis[son[y]]!=dis[x]+1||!val[y]) continue;
		ll tmp=find(son[y],min(low,val[y]));
		val[y]-=tmp,val[y^1]+=tmp,res+=tmp,low-=tmp;
		if (!low) break;
	}
	if (!y) dis[x]=-1;
	return res;
}

bool dinic(ll lim){
	//printf("%lld
",lim);
	memset(now,0,sizeof(now)),tot=1;ll flow=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (!((i+j)&1)){
				ins(S,id(i,j),lim-num[i][j]),flow+=(lim-num[i][j]);
				for (int k=0;k<4;k++){
					int nx=i+dx[k],ny=j+dy[k];
					if (nx>0&&nx<=n&&ny>0&&ny<=m)
						ins(id(i,j),id(nx,ny),inf);
				}
			}
			else ins(id(i,j),T,lim-num[i][j]);
	ll res=0;
	while (bfs()) res+=find(S,inf);
	//printf("%lld %lld
",res,flow);
	return res==flow;
}

void work(){
	if ((n*m)&1){
		X=(sum0-sum1)/(cnt0-cnt1);
		if (X>=maxs&&dinic(X)) printf("%lld
",X*cnt0-sum0);
		else puts("-1");
	}
	else{
		ll l=maxs,r=inf,mid=(l+r)>>1,ans=-1;
		//dinic(3);for (;;);
		while (l<=r){
			if (dinic(mid)) ans=mid,r=mid-1;
			else l=mid+1;
			mid=(l+r)>>1;
		}
		printf("%lld
",ans*cnt0-sum0);
	}
}

int main(){
	//freopen("game1.in","r",stdin);
	scanf("%d",&cas);
	while (cas--) init(),work();
	return 0;
}