题就不再念了

Solution

首先对棋盘进行黑白染色，像这样

然后要统计白点个数，初始白点点权和以及黑点个数与初始黑点点权和

显然的是，最终得到的值 \(X\) 可以写作

\[X=\dfrac{WhiteSum-BlackSum}{WhiteNum-BlackNum}\]

当 \(WhiteNum !=BlackNum\) 时直接判断 \(X\) 是否可行，可行则输出解，否则无解

当 \(WhiteNum==BlackNum\) 时 \(X\) 是无意义的，也就是说算不出来

但此时可以看出来，若 \(X\) 可以满足题意 那么 \(X+1\) 也满足题意(任意的白点都可以有一个与它配对的黑点一起 \(+1\) ，整个图都这么做，\(X+1\) 也就可以加出来)

说明了什么？可以二分了

二分 \(X\) 可以求出

二分的 \(Check()\) 要用到网络流

设源点为 \(S\) 汇点为 \(T\)

\(S\) 到白点连容量为 \(X-val[i][j]\) 的边，黑点到 \(T\) 连容量为 \(X-val[i][j]\) 的边，相邻的白点和黑点容量为INF

(脑补一下，白点和黑点都要加够 \(X-val[i][j]\) 次，白点和黑点之间没有限制)

如果这个图是满流的，说明 \(X\) 可行，否则不可行

这题时限40s，似乎可以用来给不法分子卡评测

注意：long long还是很慢的，memset，memcpy很耗时，刚开始浪数组开太大，卡了一个40s的TLE。。。

#include
    
     #include
     
      #include
      
       #include
       
        #define LL long long#define MAXN 100#define MAXE 10000#define INF (1LL<<60)using namespace std;LL n,m;LL kase;LL num[MAXN][MAXN];LL color[MAXN][MAXN];struct E{    LL next,to,val;}edge[MAXE];LL head[MAXE],edge_num;LL depth[MAXE],iter[MAXE];queue
        
          que;LL s,t;LL cntw,cntb,sumw,sumb;LL u[5]={0,1,-1,0,0},v[5]={0,0,0,1,-1};LL FLOW;LL MAX;LL index(LL i,LL j){    return i*m+j;}bool inmap(LL x,LL y){    return x<=n && x>=1 && y<=m && y>=1;}void addedge(LL x,LL y,LL v){    edge[++edge_num].next=head[x];    edge[edge_num].to=y;    edge[edge_num].val=v;    head[x]=edge_num;}void INIT(){    scanf("%lld%lld",&n,&m);    s=m*(n+1)+1,t=m*(n+1)+2;    cntw=cntb=sumw=sumb=0;    LL i,j;    MAX=0;    for(i=1;i<=n;i++){        for(j=1;j<=m;j++){            scanf("%lld",&num[i][j]);            MAX=max(MAX,num[i][j]);            if((j%2)^(i%2))                color[i][j]=1,cntb++,sumb+=num[i][j];            else                color[i][j]=0,cntw++,sumw+=num[i][j];        }    }}void Graph(LL x){    LL i,j;    edge_num=1;    memset(head,0,sizeof(head));    FLOW=0;    for(i=1;i<=n;i++){        for(j=1;j<=m;j++){            if(color[i][j]==0){                FLOW+=x-num[i][j];                addedge(s,i*m+j,x-num[i][j]);                addedge(i*m+j,s,0);                LL k;                for(k=1;k<=4;k++){                    LL x,y;                    x=i+u[k],y=j+v[k];                    if(inmap(x,y)){                        addedge(index(i,j),index(x,y),INF);                        addedge(index(x,y),index(i,j),0);                    }                }            }            else{                addedge(i*m+j,t,x-num[i][j]);                addedge(t,i*m+j,0);            }        }    }}void BFS(){    memset(depth,-1,sizeof(depth));    que.push(s);    depth[s]=0;    LL i;    while(!que.empty()){        LL fro=que.front();que.pop();        for(i=head[fro];i;i=edge[i].next){            if(edge[i].val>0 && depth[edge[i].to]==-1){                depth[edge[i].to]=depth[fro]+1;                que.push(edge[i].to);            }        }    }}LL DFS(LL x,LL f){    if(x==t)        return f;    for(LL &i=iter[x];i;i=edge[i].next){        if(edge[i].val>0 && depth[edge[i].to]==depth[x]+1){            LL tmp=DFS(edge[i].to,min(f,edge[i].val));            if(tmp>0){                edge[i].val-=tmp;                edge[i^1].val+=tmp;                return tmp;            }        }    }    return 0;}LL Dinic(){    LL re=0;    while(true){        BFS();        if(depth[t]<0)            break;        LL tmp;        memcpy(iter,head,sizeof(head));        while(true){            tmp=DFS(s,INF);            if(tmp<=0){                break;            }            re+=tmp;        }    }    return re;}bool check(LL x){    return FLOW==x;}void PLAN1(){    LL x=(sumw-sumb)/(cntw-cntb);    if(x
         
          >1; Graph(mid); LL tmp=Dinic(); if(check(tmp)) r=mid-1; else l=mid+1; } printf("%lld\n",l*cntw-sumw);}void solve(){ if(cntw!=cntb){ PLAN1(); } else{ if(sumw!=sumb){ printf("-1\n"); return; } else PLAN2(); }}int main(){ freopen("bzoj.in","r",stdin); freopen("out.out","w",stdout); scanf("%lld",&kase); while(kase--){ INIT(); solve(); } return 0;}