题：https://www.luogu.com.cn/problem/P5038
题意：给定n*m矩阵，每个位置都有初值，每次操作是选定相邻的俩个位置都加1，问最少执行多少次操作能让所有位置的值相同
分析：相邻我们就要想到先染色，相邻不同色。假设白格nw个，总值sumw，黑格nb个，黑格sumb个；
那么就有这么一个强条件：（设最终的值为x）x*nw-sumw==x*nb-sumb（因为选定一个黑格加1必定伴随着一个白格加1，白格同理，那么他们的增量必定相同）
得到x的式子：x=（sumw-sumb）/（nw-nb），当nw！=nb时，x仅有可能一解，这种情况要让x的值大于初值中的最大值再check一下是否合法；
当nw==nb时，当sumw！=sumb时无解，反之，我们假设存在res的解，那么res+1必定也能满足题意（因为黑格白格相同那我就可以让每一个位置加1）所以用二分check；
check写法，二分图：一种颜色向s连x-a[i][j]容量的边；
另一种颜色向t连x-a[i][j]容量的边；
连s的点 i 向连t的点 j（i和j在矩阵上位置相邻）连容量为inf的边，判断是否满流；
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back const int inf=0x3f3f3f3f; const ll INF=(1ll<<40); const int M=4e5+5; const int N=2e3+3; int tot,s,t,n,m; struct node{ int u,v,nextt; ll w; }e[M<<1]; int head[N],deep[N],cur[N],col[50][50]; int a[50][50]; int nex[]={0,0,1,-1}; int ney[]={1,-1,0,0}; void addedge(int u,int v,ll w){ e[tot].v=v; e[tot].w=w; e[tot].nextt=head[u]; head[u]=tot++; e[tot].v=u; e[tot].w=0; e[tot].nextt=head[v]; head[v]=tot++; } bool bfs(){ for(int i=0;i<=t;i++) deep[i]=0; queue<int>que; while(!que.empty()) que.pop(); que.push(s); deep[s]=1; while(!que.empty()){ int u=que.front(); que.pop(); for(int i=head[u];~i;i=e[i].nextt){ int v=e[i].v; if(e[i].w>0&&deep[v]==0){ deep[v]=deep[u]+1; if(v==t) return true; que.push(v); } } } return deep[t]!=0; } ll dfs(int u,ll fl){ if(u==t) return fl; ll ans=0,x=0; for(int i=cur[u];~i;i=e[i].nextt){ int v=e[i].v; if(e[i].w>0&&deep[v]==deep[u]+1){ x=dfs(v,min(fl-ans,e[i].w)); e[i].w-=x; e[i^1].w+=x; ans+=x; if(ans==fl) return ans; if(e[i].w) cur[u]=i; } } if(ans==0) deep[u]=0; return ans; } ll dinic(){ ll res=0ll; while(bfs()){ for(int i=0;i<=t;i++) cur[i]=head[i]; res+=dfs(s,INF); } return res; } bool check(ll x){ tot=0; ll sum=0; s=0,t=n*m+1; for(int i=0;i<=t;i++) head[i]=-1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(col[i][j]) addedge(s,(i-1)*m+j,x-a[i][j]),sum+=x-a[i][j]; else addedge((i-1)*m+j,t,x-a[i][j]); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) if(col[i][j]) for(int k=0;k<4;k++){ int tx=i+nex[k]; int ty=j+ney[k]; if(tx>=1&&tx<=n&&ty>=1&&ty<=m) addedge((i-1)*m+j,(tx-1)*m+ty,INF); } } ///cout<<"@@"<<endl; if(dinic()==sum) return 1; return 0; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); int maxx=0; int nb=0,nw=0; ll sumb=0,sumw=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); col[i][j]=(i+j)&1; if(col[i][j]==1) nw++,sumw+=a[i][j]; else nb++,sumb+=a[i][j]; maxx=max(maxx,a[i][j]); } if(nb!=nw){ ll x=(sumb-sumw)/(nb-nw); if(x>=maxx&&check(x)){ printf("%lld ",x*nw-sumw); } else puts("-1"); } else{ if(sumb!=sumw){ puts("-1"); } else{ ll l=maxx,r=INF,res=-1; while(l<=r){ ll midd=(l+r)>>1; if(check(midd)) res=midd,r=midd-1; else l=midd+1; } if(res==-1) puts("-1"); else printf("%lld ",1ll*res*nw-sumw); } } } return 0; }