网络流。
确实是网络流题目做太少，完全没往这方面去想。。。
对棋盘进行黑白相间染色，如果记s0表示黑格子数字和，s1表示白格子数字和，t1表示黑格子数量，t2表示白格子数量，操作之后数字全都是x，那么因为黑白格子的操作次数肯定一样，有 x∗t1−s1=x∗t0−s0 可以得到 x=s1−s0t1−t0
如果 t1≠t2 那么x是唯一的，直接判断即可 否则假设x可行，那么任何大于x的数一定可行，于是二分即可
至于怎么判断，网络流！ 源点->所有黑格 容量是格子的数字 黑格->相邻白格 容量无限大 所有白格->汇点 容量是格子的数字 判断最大流是否等于x与所有数字差的和即可
#include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define N 42 #define INF (1LL<<50) using namespace std; struct edge{int next,to;long long v;}e[N*N*4*2]; long long s[2], a[N][N]; int S, T, last[N*N], p_cnt, t[2]; int n, m, cnt, pack[N][N], dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0}, level[N*N]; bool color[N][N]; void add(int a, int b, long long w) { e[++cnt]=(edge){last[a],b,w}; last[a]=cnt; e[++cnt]=(edge){last[b],a,0}; last[b]=cnt; } bool bfs() { queue<int> q; memset(level,-1,sizeof(level)); q.push(S); level[S]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i = last[x]; i; i=e[i].next) { int y=e[i].to; if(e[i].v && level[y]==-1) { level[y]=level[x]+1; q.push(y); } } } return level[T]!=-1; } long long dfs(int x, long long f) { long long re=0; if(x==T)return f; for(int i = last[x]; i; i=e[i].next) { int y=e[i].to; if(level[x]+1!=level[y] || !e[i].v)continue; long long use=dfs(y,min(f-re,e[i].v)); e[i].v-=use; e[i^1].v+=use; re+=use; if(re==f)return f; } if(!re)level[x]=-1; return re; } long long dinic() { long long re=0; while(bfs()) re+=dfs(S,INF); return re; } bool check(long long x) { memset(last,0,sizeof(last)); cnt=1; S=0, T=n*m+2; long long pre=0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { if(color[i][j]) { pre+=x-a[i][j]; add(S,pack[i][j],x-a[i][j]); for(int k = 0; k < 4; k++) { int nx=i+dx[k], ny=j+dy[k]; if(nx<1||ny<1||nx>n||ny>m)continue; add(pack[i][j],pack[nx][ny],INF); } } else add(pack[i][j],T,x-a[i][j]); } return dinic()==pre; } int main() { int T; scanf("%d",&T); while(T--) { p_cnt=0; memset(s,0,sizeof(s)); memset(t,0,sizeof(t)); long long mx=0; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { scanf("%lld",&a[i][j]); mx=max(mx,a[i][j]); pack[i][j]=++p_cnt; } for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { color[i][j]=(i+j)&1; s[color[i][j]]+=a[i][j]; t[color[i][j]]++; } if(t[0]!=t[1]) { long long x=(s[0]-s[1])/(t[0]-t[1]); if(x<mx)printf("-1\n"); else printf("%lld\n",check(x)?(x*t[0]-s[0]):-1); } else { if(s[0]!=s[1])printf("-1\n"); else { long long l = mx, r = INF; while(l<r) { long long mid=(l+r)>>1; if(check(mid))r=mid; else l=mid+1; } printf("%lld\n",l*t[1]-s[1]); } } } }