BZOJ 2756: [SCOI2012]奇怪的游戏网络流/二分-白红宇

BZOJ 2756: [SCOI2012]奇怪的游戏网络流/二分

阅读量：6103 次

发布时间：2019-06-20

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

2756: [SCOI2012]奇怪的游戏

Time Limit: 40 Sec Memory Limit: 128 MB

Submit: 1594 Solved: 396

[][][]

Description

Blinker最近喜欢上一个奇怪的游戏。

这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻

的格子，并使这两个数都加上 1。

现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同

一个数则输出-1。

Input

输入的第一行是一个整数T，表示输入数据有T轮游戏组成。

每轮游戏的第一行有两个整数N和M，分别代表棋盘的行数和列数。

接下来有N行，每行 M个数。

Output

对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。

Sample Input

2 2

1 2

2 3

3 3

1 2 3

2 3 4

4 3 2

Sample Output

-1

HINT

【数据范围】

对于30%的数据，保证 T<=10，1<=N,M<=8

对于100%的数据，保证 T<=10，1<=N,M<=40，所有数为正整数且小于1000000000

题解：

我们把整个棋盘的格子分为两种，一种为白，一种为黑

然后设最后的格子全部变成了x，那么x*num1-sum1=x*num2-sum2;

其中num1为白色格子数量，num2位黑色格子数量，sum1为白色格子权值和

那么，我们可以得到x=(sum1-sum2)/(num1-num2)

当num1!=num2的时候，我们可以直接通过最大流来check

否则的话，我们就二分枚举答案

首先如果x能够成立的话，那么大与x的所有数都能成立，只要再铺一层就好，而且num1+num2%2==0

所以题目的思路还是比较简单的~

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #define inf (1LL<<50)#define pa pair
                
                 #define ll long long #define p(x,y) (x-1)*m+yusing namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}ll s0,s1;int c0,c1;int test,n,m,cnt,S,T;int xx[4]={ 0,0,1,-1},yy[4]={ 1,-1,0,0};int a[45][45];int last[2005],h[2005],q[2005],cur[2005];bool color[45][45];struct edge{ int to,next;ll v;}e[20005];void insert(int u,int v,ll w){ e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;}bool bfs(){ int head=0,tail=1; memset(h,-1,sizeof(h)); q[0]=S;h[S]=0; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; } } return h[T]!=-1;}ll dfs(int x,ll f){ if(x==T)return f; ll w,used=0; for(int i=cur[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(f-used,e[i].v)); e[i].v-=w;e[i^1].v+=w; if(e[i].v)cur[x]=i; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used;}ll dinic(){ ll tmp=0; while(bfs()) { for(int i=S;i<=T;i++)cur[i]=last[i]; tmp+=dfs(S,inf); } return tmp;}bool check(ll x){ memset(last,0,sizeof(last)); cnt=1;S=0;T=n*m+1; ll tot=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(color[i][j]) { insert(S,p(i,j),x-a[i][j]);tot+=x-a[i][j]; for(int k=0;k<4;k++) { int nowx=i+xx[k],nowy=j+yy[k]; if(nowx<1||nowy<1||nowx>n||nowy>m)continue; insert(p(i,j),p(nowx,nowy),inf); } } else insert(p(i,j),T,x-a[i][j]); if(dinic()==tot)return 1; return 0;}int main(){ test=read(); while(test--) { c0=c1=s0=s1=0; n=read();m=read(); int mx=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=read(),color[i][j]=(i+j)&1; mx=max(mx,a[i][j]); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(color[i][j])s1+=a[i][j],c1++; else s0+=a[i][j],c0++; if(c0!=c1) { ll x=(s0-s1)/(c0-c1); if(x>=mx) if(check(x)) { printf("%lld\n",x*c1-s1); continue; } puts("-1"); } else { ll l=mx,r=inf; while(l<=r) { ll mid=(l+r)>>1; if(check(mid))r=mid-1; else l=mid+1; } printf("%lld\n",(ll)l*c1-s1); } } return 0;}