【网络流】【1010】【棋盘加数】-白红宇

【网络流】【1010】【棋盘加数】

阅读量：5887 次

发布时间：2019-06-19

本文共 2991 字，大约阅读时间需要 9 分钟。

题目大意

一个 N*M 的棋盘上每个格子有一个数。每次选择两个相邻的格子，并使这两个数都加上 1。问最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。

显然有黑白染色的特征

显然是二分图

黑色和白色的数值差永远不变

如果知道变成什么数，可以用网络流来判断是否可以

做法

如果N或M为偶数可以二分+网络流解决

如果N和M都为奇数可以利用以下等式

（黑色格子数-白色格子数）*最终情况格子的值=黑色初始格子总值-白色初始格子总值
得到最终情况格子的值，所以为奇数的时候是一个确定的值

坑点

注意MAXN，MAXM的确定，小了的话，会超时，很难发现是因为这个超时的！！！

long long

代码

#include 
     
        #include 
      
         #include 
       
          #include 
        
           #include 
         
            #include 
          
            #include 
           
            #include 
            
             #include 
             
              #define oo 0x13131313 using namespace std;const int MAXN=2000+5;const int MAXM=10000;long long INF=1LL<<50;int ok=1;int fx[5]={ 0,0,0,1,-1},fy[6]={ 0,1,-1,0,0};struct Edge{ long long to,next,cap,flow; void get(long long a,long long b,long long c,long long d) { to=a;next=b;cap=c;flow=d; }}edge[MAXM];long long tol;long long head[MAXN];long long gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];void init(){ tol=0; memset(head,-1,sizeof(head));}//¦Ì£¤Ï¨°¨ª¼¨¨y¸ö2Î¨ºy¡ê¬ÎTÏ¨°¨ª¼ËÄ¸ö2Î¨ºyvoid addedge(long long u,long long v,long long w,long long rw=0){ edge[tol].get(v,head[u],w,0);head[u]=tol++; edge[tol].get(u,head[v],rw,0);head[v]=tol++;}long long sap(long long start,long long end,long long N){ memset(gap,0,sizeof(gap)); memset(dep,0,sizeof(dep)); memcpy(cur,head,sizeof(head)); long long u=start; pre[u]=-1; gap[0]=N; long long ans=0; while(dep[start]
              
               edge[i].cap-edge[i].flow) Min=edge[i].cap-edge[i].flow; for(long long i=pre[u];i!=-1;i=pre[edge[i^1].to]) { edge[i].flow+=Min; edge[i^1].flow-=Min; } u = start; ans+=Min; continue; } bool flag=false; long long v; for(long long i=cur[u];i !=-1;i=edge[i].next) { v=edge[i].to; if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]) { flag=true; cur[u]=pre[v]=i; break; } } if(flag) { u=v; continue; } long long Min=N; for(long long i=head[u];i!=-1;i=edge[i].next) if(edge[i].cap-edge[i].flow&&dep[edge[i].to]
               
                >N>>M; for(long long i=1;i<=N;i++) for(long long j=1;j<=M;j++) { scanf("%I64d",&MAP[i][j]); sum+=MAP[i][j]; if((i+j)%2==0) b=b+MAP[i][j],nb++; else w=w+MAP[i][j],nw++; }}void creatgraph(long long c){ init(); s=0;t=N*M+1; //s-> && ->oo for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) { if((i+j)%2==0) { if(c-MAP[i][j]>=0) addedge(s,(i-1)*M+j,c-MAP[i][j]); else ok=0; for(int k=1;k<=4;k++) { long long xx=i+fx[k],yy=j+fy[k]; if(1<=xx&&xx<=N&&1<=yy&&yy<=M) { //debug // printf("%d %d->%d %d\n",i,j,xx,yy); addedge((i-1)*M+j,(xx-1)*M+yy,INF); } } } } //->t for(long long i=1;i<=N;i++) for(long long j=1;j<=M;j++) { if((i+j)%2==1) if(c-MAP[i][j]>=0) addedge((i-1)*M+j,t,c-MAP[i][j]); else ok=0; } }void solve1(){ if(w!=b) { printf("-1\n"); return ; } else { long long l=0,r=1LL<<40; while(l
                
                 w) { long long m=b-w; creatgraph(m); if(sap(s,t,N*M+2)==(N*M*m-sum)/2) printf("%I64d\n",(N*M*m-sum)/2); else printf("-1\n"); } else printf("-1\n");} int main(){// freopen("a.in","r",stdin); long long T; cin>>T; while(T--) { ok=1; input(); if(N%2==0||M%2==0) solve1(); else solve2(); } }