学步园

题目大意：给出一个棋盘，上面有一些数字，每一次可以将相邻的两个数字一起加一。问最少的次数使得整个棋盘上的数字都相等。

思路：基础思路：二分最少的相等的数字。将棋盘黑白染色，每次操作一定会使一个黑子和一个白子加1，建立二分图，S向所有白点连边，所有黑点向T连边，流量为每个点到达需要相等数字的需求大小。相邻的黑点和白点连边，f:INF。然后跑最大流看是否满流就可以了。

但是这个题需要多想一些。

因为每次会让黑点和白点同时加1,所以suma和sumb的差是不会改变的。

若m*n是偶数，那么黑点白点数量相同，若suma！=sumb则无解。

若m*n是奇数，那么可以O(1)算出可行的相等的数字，直接判断就可以出解了。

剩下的情况可以证明二分的正确性，如果可以都等于k，那么剪掉一层就变k-1了，由于m*n是偶数，所以肯定存在一种方案剪掉一层。

CODE：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 2010
#define MAXE 210010
#define S 0
#define T (MAX - 1)
#define INF (1ll << 55)
using namespace std;
const int dx[] = {0,1,-1,0,0};
const int dy[] = {0,0,0,1,-1};

long long all_flow;

struct MaxFlow{
	int head[MAX],total;
	int next[MAXE],aim[MAXE];
	long long flow[MAXE];
	int deep[MAX];
	
	void Reset() {
		total = 1;
		memset(head,0,sizeof(head));
	}
	void Add(int x,int y,long long f) {
		next[++total] = head[x];
		aim[total] = y;
		flow[total] = f;
		head[x] = total;
	}
	void Insert(int x,int y,long long f) {
		if(x == S)	all_flow += f;
		Add(x,y,f);
		Add(y,x,0);
	}
	bool BFS() {
		static queue<int> q;
		while(!q.empty())	q.pop();
		memset(deep,0,sizeof(deep));
		deep[S] = 1;
		q.push(S);
		while(!q.empty()) {
			int x = q.front(); q.pop();
			for(int i = head[x]; i; i = next[i])
				if(flow[i] && !deep[aim[i]]) {
					deep[aim[i]] = deep[x] + 1;
					q.push(aim[i]);
					if(aim[i] == T)	return true;
				}
		}
		return false;
	}
	long long Dinic(int x,long long f) {
		if(x == T)	return f;
		long long temp = f;
		for(int i = head[x]; i; i = next[i])
			if(flow[i] && temp && deep[aim[i]] == deep[x] + 1) {
				long long away = Dinic(aim[i],min(flow[i],temp));
				if(!away)	deep[aim[i]] = 0;
				flow[i] -= away;
				flow[i^1] += away;
				temp -= away;
			}
		return f - temp;
	}
}solver;

int _T,m,n,cnt;
int src[50][50],num[50][50];
bool color[50][50];
long long black,white,start;
int b_cnt,w_cnt;

inline void Initialize()
{
	black = white = cnt = 0;
	b_cnt = w_cnt = 0;
	start = 0;
	memset(color,0,sizeof(color));
	memset(num,0,sizeof(num));
	color[1][1] = true;
	for(int i = 2; i <= m; ++i)
		color[i][1] = !color[i - 1][1];
	for(int i = 1; i <= m; ++i)
		for(int j = 2; j <= n; ++j)
			color[i][j] = !color[i][j - 1];
}

inline bool Judge(long long ans)
{
	solver.Reset();
	all_flow = 0;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			color[i][j] ? solver.Insert(S,num[i][j],ans - src[i][j]):solver.Insert(num[i][j],T,ans - src[i][j]);
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j) {
			if(!color[i][j])	continue;
			for(int k = 1; k <= 4; ++k) {
				int fx = i + dx[k],fy = j + dy[k];
				if(!fx || !fy || fx > m || fy > n)	continue;
				solver.Insert(num[i][j],num[fx][fy],INF);
			}
		}
	long long max_flow = 0;
	while(solver.BFS())
		max_flow += solver.Dinic(S,INF);
	return max_flow == all_flow;
}

int main()
{
	for(cin >> _T; _T--;) {
		scanf("%d%d",&m,&n);
		Initialize();
		for(int i = 1; i <= m; ++i)
			for(int j = 1; j <= n; ++j) {
				scanf("%d",&src[i][j]),num[i][j] = ++cnt;
				start = max(start,(long long)src[i][j]);
			}
		for(int i = 1; i <= m; ++i)
			for(int j = 1; j <= n; ++j) {
				color[i][j] ? white += src[i][j]:black += src[i][j];
				color[i][j] ? ++w_cnt:++b_cnt;
			}
		if(w_cnt != b_cnt) {
			long long mid = (black - white) / (b_cnt - w_cnt);
			if(mid >= start && Judge(mid))
				printf("%lld\n",((long long)m * n * mid - white - black) >> 1);
			else	puts("-1");
		}
		else {
			if(black != white) {
				puts("-1");
				continue;
			}
			long long l = start,r = INF,ans = -1;
			while(l <= r) {
				long long mid = (l + r) >> 1;
				if(Judge(mid))
					r = mid - 1,ans = mid;
				else	l = mid + 1;
			}
			if(ans + 1)
				printf("%lld\n",(ans * m * n - white - black) >> 1);
			else	puts("-1");
		}
	}
	return 0;
}