Bzoj2756 [scoi2012]奇怪的游戏

Posted by yjjr's blog on February 6, 2018

标签:网络流,最大流

题目

题目传送门

Description

Blinker最近喜欢上一个奇怪的游戏。 这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻 的格子,并使这两个数都加上 1。 现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同 一个数则输出-1。

Input

输入的第一行是一个整数T,表示输入数据有T轮游戏组成。 每轮游戏的第一行有两个整数N和M, 分别代表棋盘的行数和列数。 接下来有N行,每行 M个数。

Output

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

Sample Input

2

2 2

1 2

2 3

3 3

1 2 3

2 3 4

4 3 2 Sample Output

2

-1

HINT

【数据范围】

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

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

分析

将棋盘进行黑白点染色,设黑点个数为c1,总和为$ s1=\sum a[i][j] $

白点个数为c2,总和为 $ s2=\sum a[i][j] $

设最后所有的格子内都变成x

那么列出方程

$ c1x-s1=c2x-s2 $

$ x=(s1-s2)/(c1-c2) $

解出x之后可以用网络流检验答案是否可行

建图过程:

将超级源点S=0向每个黑点连边流量为x-a[i][j],黑点和白点之间连边流量为无穷大,白点再和超级汇点连边流量为x-a[i][j]

最后看总的流量是不是$ \sum x-a[i][j] $

如果符合条件那么输出答案x,否则输出-1

但是当c1=c2时,就无法解得x,显然存在一个最小值x,满足k>=x都是一个合法的解

那么可以二分答案x(每点最终权值)然后同样用最大流dinic解决

这题调试了大半天,原因竟是数组开小,可是神奇的bzoj提醒我TLE,明明实际上是RE啊,bzoj=玄学OJ,有没有大佬知道原因的啊qwq

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define inf 1LL<<50
#define p(x,y) (x-1)*m+y
using namespace std;
inline 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;
}
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll s1,s2,ans;
int c1,c2,S,T,n,m,cnt,Que,last[2006],h[2006],que[2006],a[46][46];
bool col[46][46];
struct edge{int to,next;ll v;}e[20006];
  
void insert(int u,int v,ll w){
    e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
    e[++cnt]=(edge){u,last[v],0};last[v]=cnt;
}
  
bool bfs()
{
    int head=0,tail=1,now;
    mem(h,-1);
    que[0]=S;h[S]=0;
    while(head<tail){
        now=que[head++];
        reg(now)
            if(e[i].v&&h[e[i].to]==-1){
                h[e[i].to]=h[now]+1;
                que[tail++]=e[i].to;
            }
    }
    return h[T]!=-1;
}
  
inline ll dfs(int x,ll f)
{
    if(x==T)return f;
    ll w,used=0;
    reg(x)
        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;
            used+=w;if(used==f)return f;
        }
    if(!used)h[x]=-1;
    return used;
}
  
inline ll dinic(){
    ll temp=0;
    while(bfs())temp+=dfs(S,inf);
    return temp;
}
bool check(ll x)
{
    mem(last,0);mem(e,0);
    cnt=1;S=0;T=n*m+1;
    ll tot=0;
    rep(i,1,n)
        rep(j,1,m)
            if(col[i][j]){
                insert(S,p(i,j),x-a[i][j]);tot+=x-a[i][j];
                rep(k,0,3){
                    int nx=i+dx[k],ny=j+dy[k];
                    if(nx<1||nx>n||ny<1||ny>m)continue;
                    insert(p(i,j),p(nx,ny),inf);
                }
            }
            else insert(p(i,j),T,x-a[i][j]);
    if(dinic()==tot)return 1;else return 0;
}
int main()
{
    Que=read();
    while(Que--){
        int Max=0;
        n=read(),m=read();
        c1=c2=s1=s2=0;
        rep(i,1,n)
            rep(j,1,m){
                a[i][j]=read();
                col[i][j]=(i+j)&1;Max=max(Max,a[i][j]);
            }
        rep(i,1,n)
            rep(j,1,m)
                if(col[i][j])s2+=a[i][j],c2++;
                else s1+=a[i][j],c1++;
        if(c1!=c2){
            ll x=(s1-s2)/(c1-c2);
            if(x>=Max)
                if(check(x)){printf("%lld\n",(ll)x*c2-s2);continue;}
            puts("-1");
        }
        else{
            if(s1!=s2){puts("-1");continue;}
            ll l=Max,r=inf;
            while(l<=r){
                ll mid=(l+r)/2;
                if(check(mid))r=mid-1;else l=mid+1;
            }
            printf("%lld\n",(ll)l*c2-s2);
        }
    }
    return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr