BZOJ_2756.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN=1600+10;
const int SIZE=50;
const LL inf=1ll<<50ll;

struct Edge {
	int v;
	LL cap;
	Edge *next, *op;
	Edge(){}
	Edge(int _v, LL _c, Edge* _n):v(_v), cap(_c), next(_n){}
};

Edge *E[MAXN];
LL map[SIZE][SIZE];
int idx[SIZE][SIZE];
int Q[MAXN], level[MAXN];
int N, M, S, T;

inline void addedge(int u, int v, LL a) {
	E[u]=new Edge(v, a, E[u]);
	E[v]=new Edge(u, 0, E[v]);
	E[u]->op=E[v]; E[v]->op=E[u];
}

inline bool dinic_bfs() {
	memset(level, -1, sizeof(level));
	level[S]=0; Q[0]=S;
	for (int h=0, t=1; h<t; h++) {
		int u=Q[h], v;
		for (Edge *p=E[u]; p; p=p->next)
			if (level[v=p->v]==-1&&p->cap>0) {
				level[v]=level[u]+1;
				Q[t++]=v;
			}
	}
	return (level[T]!=-1);
}

LL dinic_dfs(int u, LL low) {
	if (u==T) return low;
	LL ret=0, tmp; int v;
	for (Edge *p=E[u]; p&&ret<low; p=p->next) 
		if (level[v=p->v]==level[u]+1&&p->cap>0) {
			if (tmp=dinic_dfs(v, min(low-ret, p->cap))) {
				ret+=tmp, p->cap-=tmp, p->op->cap+=tmp;
			}
		}
	if (!ret) level[u]=-1; return ret;
}

inline LL dinic() {
	LL maxflow=0, t;
	while (dinic_bfs()) {
		while (t=dinic_dfs(S, inf)) maxflow+=t;
	}
	return maxflow;
}

bool solve(LL target, LL step) {
	memset(E, 0, sizeof(E));
	S=0; T=N*M+1;
	for (int i=1; i<=N; i++)
		for (int j=1; j<=M; j++) {
			if (target<map[i][j]) return false;
			if ((i+j)&1) addedge(idx[i][j], T, target-map[i][j]);
			else {
				addedge(S, idx[i][j], target-map[i][j]);
				if (i>1) addedge(idx[i][j], idx[i-1][j], inf);
				if (j>1) addedge(idx[i][j], idx[i][j-1], inf);
				if (i<N) addedge(idx[i][j], idx[i+1][j], inf);
				if (j<M) addedge(idx[i][j], idx[i][j+1], inf);
			}
		}
	return (dinic()==step);
}

int main() {
	int t; scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &N, &M);
		LL s1=0, s2=0, c1=0, c2=0; int cnt=0;
		for (int i=1; i<=N; i++) 
			for (int j=1; j<=M; j++) {
				scanf("%lld", &map[i][j]);
				idx[i][j]=++cnt;
				if ((i+j)&1) s1+=map[i][j], c1++;
				else s2+=map[i][j], c2++;
			}
		if (c1!=c2) {
			LL x=(s1-s2)/(c1-c2);
			if ((s1-s2)%(c1-c2)==0&&solve(x, x*c1-s1)) printf("%lld\n", x*c1-s1);
			else puts("-1");
		}
		else {
			if (s1!=s2) puts("-1");
			else {
				LL left=0, right=inf;
				while (left<right) {
					LL mid=(left+right)>>1;
					if (solve(mid, mid*c1-s1)) right=mid;
					else left=mid+1;
				}
				printf("%lld\n", right*c1-s1);
			}
		}
	}
	return 0;
}