Time:2016.08.15 Author:xiaoyimi 转载注明出处谢谢
传送门 思路： 首先考虑黑白染色 设最终所有格子的数字都是x 那么到最后黑格子和白格子的增量都是一样的 设起始黑格子共有num1个，数字总和为sum1，白格子共有num2个，数字总和为sum2 那么num1*x-sum1=num2*x-sum2 然后呢？ 分类讨论 黑白点数不相等时（num1!=num2）（即n*m为奇数时） 显然有 |num1−num2|=1 x=sum1−sum2num1−num2 所以我们只要判断最终答案是不是x就可以了 黑白点数相等时（num1=num2）（即n*m为偶数时） x就不唯一了 我们要求出最小的x 显然x+1,x+2..都是可以了 考虑二分答案 如何用网络流判断x？ S向黑点(i,j)连边，流量为x-w(i,j) 白点(i,j)连边，流量为x-w(i,j) 黑点向四周的白点连边，流量inf 答案可行的条件是满流 也就是最大流等于∑x-w(i,j) 最终输出答案就是x*num1-sum1 注意： 无解条件 n*m为奇数时x小于max(w(i,j))或网络流check失败 n*m为偶数时sum1!=sum2或网络流check失败 代码：
#include<cstdio> #include<iostream> #include<queue> #include<cstring> #define LL long long #define pd(i,j) (1<=i&&i<=n&&1<=j&&j<=m) #define inf 1LL<<60 using namespace std; int T,n,m,s,t,tot; int a[42][42],first[1605],dis[1605]; int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0}; queue <int> q; struct edge{ int v,next; LL w; }e[20005]; int in() { int t=0;char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) t=(t<<1)+(t<<3)+ch-48,ch=getchar(); return t; } void add(int x,int y,LL z) { e[++tot]=(edge){y,first[x],z};first[x]=tot; e[++tot]=(edge){x,first[y],0};first[y]=tot; } bool bfs() { memset(dis,0,sizeof(dis)); dis[s]=1;q.push(s); for (;!q.empty();q.pop()) { int k=q.front(); for (int i=first[k];i;i=e[i].next) if (!dis[e[i].v]&&e[i].w) dis[e[i].v]=dis[k]+1, q.push(e[i].v); } return dis[t]; } LL dfs(int x,LL mx) { if (x==t) return mx; LL k,used=0; for (int i=first[x];i;i=e[i].next) if (dis[e[i].v]==dis[x]+1) { k=dfs(e[i].v,min(e[i].w,mx-used)); e[i].w-=k;e[i^1].w+=k; used+=k; if (used==mx) return mx; } if (!used) dis[x]=0; return used; } bool check(LL flow) { memset(first,0,sizeof(first)); tot=1; LL cnt=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (i+j&1) { add(s,(i-1)*m+j,flow-a[i][j]); cnt+=flow-a[i][j]; for (int k=0;k<4;k++) if (pd(i+dx[k],j+dy[k])) add((i-1)*m+j,(i-1+dx[k])*m+j+dy[k],inf); } else add((i-1)*m+j,t,flow-a[i][j]); } while (bfs()) cnt-=dfs(s,inf); return !cnt; } main() { for (T=in();T;T--) { n=in();m=in(); t=n*m+1; int mx=0; LL sum1=0,sum2=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { a[i][j]=in(), mx=max(mx,a[i][j]); if (i+j&1) sum1+=a[i][j]; else sum2+=a[i][j]; } if (n*m&1) if(sum2-sum1>=mx&&check(sum2-sum1)) printf("%lld\n",(sum2-sum1)*(n*m/2)-sum1); else puts("-1"); else { if (sum2!=sum1) {puts("-1");continue;} LL l=mx,r=inf,mid,ans=0; for (mid=l+r>>1;l<=r;mid=l+r>>1) if (check(mid)) r=mid-1,ans=mid; else l=mid+1; printf("%lld\n",ans*(n*m/2)-sum1); } } }