「SCOI2012」奇怪的游戏 - 最大流+流量分配/匹配模型

题目大意

    Blinker最近喜欢上一个奇怪的游戏。
    这个游戏在一个$N*M$的棋盘上玩，每个格子有一个数。每次Blinker会选择两个相邻的格子，并使这两个数都加上$1$。
现在Blinker想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出$-1$。

---

题目分析

考虑已经知道最后全部变为$x$。
将原棋盘染色，显然每次增加会将黑白的数字同时$+1$，即黑白的差不变。
设黑色格子的个数是$num_1$，白色格子的个数是$num_2$，黑色格子数字和为$sum_1$，白色格子数字和为$sum_2$。
可得：$num_1\times x-sum_1=num_2\times x-sum_2$。
解得：$x=\frac{sum_1-sum_2}{num_1-num_2}$。
当$num_1\neq num_2$时，可以解出$x$，用网络流判断一下是否合法。
当$num_1=num_2$时，若满足$sum_1=sum_2$，$x$均合法，可二分$x$，用网络流判断合法性。

建模方式：
流量分配/匹配模型。
从源点向每个黑点连接容量为$x-v\quad(v$是原来的数$)$的边，从白点向汇点连接容量为$x-v\quad(v$是原来的数$)$的边，从黑点向相邻的白点连接容量为$inf$的边。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=1605;
 
struct Edge {
	int from,to;
	LL cap,flow;
	Edge(int x=0,int y=0,LL c=0,LL f=0):from(x),to(y),cap(c),flow(f) {}
};
 
struct Dinic {
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool vst[maxn];
	int dist[maxn],cur[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,LL v) {
		edges.push_back(Edge(x,y,v,0));
		edges.push_back(Edge(y,x,0,0));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bfs() {
		memset(vst,0,sizeof(vst));
		memset(dist,0,sizeof(dist));
		queue<int>Q;
		Q.push(t); //反向层次图
		vst[t]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(!vst[Next]&&e.cap>e.flow) { 
					vst[Next]=1;
					dist[Next]=dist[Now]+1;
					Q.push(Next);
				}
			}
		}
		return vst[s];
	}
	LL dfs(int Now,LL a) {
		if(Now==t||a==0)return a;
		LL flow=0;
		for(int& i=cur[Now]; i<G[Now].size(); i++) {
			Edge& e=edges[G[Now][i]];
			int Next=e.to;
			if(dist[Now]-1!=dist[Next])continue;
			LL nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				e.flow+=nextflow;
				edges[G[Now][i]^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	LL maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		LL flow=0;
		while(bfs()) {
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,LLONG_MAX);
		}
		return flow;
	}
} dinic;

const int Dirx[]= {0,1,-1,0,0},Diry[]= {0,0,0,1,-1};
int t,n,m,color[45][45];
LL a[45][45]; 

int id(int x,int y) {
	return (x-1)*m+y;
}

bool Check(LL Limit) {
	dinic.init(n*m+2);
	int S=n*m+1,T=n*m+2;
	LL sum=0;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			if(color[i][j]) {
				dinic.AddEdge(S,id(i,j),Limit-a[i][j]);
				sum+=Limit-a[i][j];
				for(int k=1; k<=4; k++) {
					int nx=i+Dirx[k],ny=j+Diry[k];
					if(nx<1||ny<1||nx>n||ny>m)continue;
					dinic.AddEdge(id(i,j),id(nx,ny),LLONG_MAX/2);
				}
			} else dinic.AddEdge(id(i,j),T,Limit-a[i][j]);
		}
	return dinic.maxflow(S,T)==sum;
}

int main() {
	t=Get_Int();
	while(t--) {
		n=Get_Int();
		m=Get_Int();
		LL Max=0,sum1=0,sum2=0,num1=0,num2=0;
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++) {
				a[i][j]=Get_Int();
				color[i][j]=(i+j)&1;
				if(color[i][j])sum1+=a[i][j],num1++;
				else sum2+=a[i][j],num2++;
				Max=max(Max,a[i][j]);
			}
		if(num1!=num2) {
			LL x=(sum1-sum2)/(num1-num2);
			if(x>=Max&&Check(x))printf("%lld\n",x*num1-sum1);
			else puts("-1");
		} else {
			if(sum1!=sum2) {
				puts("-1");
				continue;
			}
			LL Left=Max,Right=LLONG_MAX/2;
			while(Left<=Right) {
				LL mid=(Left+Right)>>1;
				if(Check(mid))Right=mid-1;
				else Left=mid+1;
			}
			printf("%lld\n",Left*num1-sum1);
		}
	}
	return 0;
}