网络流，我竟然没想出来黑白染色！！！
黑白染色，发现黑的增加量一定等于白的增加量，设最后格子里的数为$x$,那么$x*num1-sum1=x*num2-sum2$
如果$num1=num2$，
如果$sum1!=sum2$，无解，
否则易证若$x1$有解，任意$x>x1$均有解。
如果$num1!=num2$
$x=frac{sum1-sum2}{num1-num2}$
那么如何跑最后的答案呢，$S$向黑点，白点向$T$均连$x-val$的边，相邻黑白格连$inf$的边，看能否跑满即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define int long long 8 #define N 1605 9 #define inf 0x7ffffffff 10 using namespace std; 11 int e=2,head[N]; 12 struct edge{ 13 int u,v,f,next; 14 }ed[N<<4]; 15 void add(int u,int v,int f){ 16 ed[e].u=u;ed[e].v=v;ed[e].f=f; 17 ed[e].next=head[u];head[u]=e++; 18 ed[e].u=v;ed[e].v=u;ed[e].f=0; 19 ed[e].next=head[v];head[v]=e++; 20 } 21 int dep[N]; 22 int n,m,tim,num1,num2,sum1,sum2,S,T; 23 int a[44][44],id[44][44],maxn; 24 bool bfs(){ 25 memset(dep,0,sizeof dep); 26 queue<int> q; 27 q.push(S);dep[S]=1; 28 while(!q.empty()){ 29 int x=q.front();q.pop(); 30 for(int i=head[x];i;i=ed[i].next){ 31 if(ed[i].f&&!dep[ed[i].v]){ 32 dep[ed[i].v]=dep[x]+1; 33 if(ed[i].v==T)return 1; 34 q.push(ed[i].v); 35 } 36 } 37 } 38 return 0; 39 } 40 int dfs(int x,int f){ 41 if(x==T||f==0)return f; 42 int ans=0; 43 for(int i=head[x];i;i=ed[i].next){ 44 if(ed[i].f&&dep[ed[i].v]==dep[x]+1){ 45 int nxt=dfs(ed[i].v,min(f,ed[i].f)); 46 ans+=nxt;f-=nxt;ed[i].f-=nxt;ed[i^1].f+=nxt; 47 } 48 if(!f)break; 49 } 50 if(!ans)dep[x]=-1; 51 return ans; 52 } 53 int dinic(){ 54 int ans=0; 55 while(bfs())ans+=dfs(S,inf); 56 return ans; 57 } 58 bool work(int x){ 59 e=2,memset(head,0,sizeof head); 60 for(int i=1;i<=n;i++){ 61 for(int j=1;j<=m;j++){ 62 if((i+j)&1){ 63 add(S,id[i][j],x-a[i][j]); 64 if(i>1)add(id[i][j],num1+id[i-1][j],inf); 65 if(i<n)add(id[i][j],num1+id[i+1][j],inf); 66 if(j>1)add(id[i][j],num1+id[i][j-1],inf); 67 if(j<m)add(id[i][j],num1+id[i][j+1],inf); 68 } 69 else add(num1+id[i][j],T,x-a[i][j]); 70 } 71 } 72 return dinic()==((x*num1)-sum1); 73 } 74 signed main(){ 75 scanf("%lld",&tim); 76 while(tim--){ 77 scanf("%lld%lld",&n,&m); 78 num1=num2=sum1=sum2=maxn=0;S=n*m+1;T=S+1; 79 for(int i=1;i<=n;i++) 80 for(int j=1;j<=m;j++){ 81 scanf("%lld",&a[i][j]); 82 if((i+j)&1)id[i][j]=++num1,sum1+=a[i][j]; 83 else id[i][j]=++num2,sum2+=a[i][j]; 84 maxn=max(maxn,a[i][j]); 85 } 86 if(num1==num2){ 87 if(sum1!=sum2)puts("-1"); 88 else{ 89 int l=maxn,r=inf,mid,ans=maxn; 90 while(l<=r){ 91 mid=(l+r)>>1; 92 if(work(mid))ans=mid,r=mid-1; 93 else l=mid+1; 94 } 95 printf("%lld ",(ans*n*m-sum1-sum2)/2); 96 } 97 } 98 else{ 99 int ans=(sum1-sum2)/(num1-num2); 100 if(ans*(num1-num2)!=(sum1-sum2)||ans<maxn)puts("-1"); 101 else{ 102 if(work(ans))printf("%lld ",(ans*n*m-sum1-sum2)/2); 103 else puts("-1"); 104 } 105 } 106 } 107 return 0; 108 }