2756: [SCOI2012]奇怪的游戏

Time Limit: 40 Sec  Memory Limit: 128 MB
Submit: 4899  Solved: 1358
[Submit][Status][Discuss]

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

【题解】首先发现一个性质…

把这个图黑白染色后是二分图。

好,如果这个二分图黑白两种颜色相等,那么如果它们初始的和不一样,那么一定GG了,因为每次操作都会把黑白两种颜色的总和+1.

先撇开颜色相等的情况。

如果颜色不等,那么我们根据最终相等的情况可以得到一个等式,可以把最终相等的值算出来。

然后发现可以用网络流验证,从源点到每个白点容量为x-a[i],黑点到汇点容量也为此,相邻的白点黑点之间容量为INF.

如果最大流等于某种颜色的增量那么就合法。

那回到颜色数目相等且总和相等的情况…最后的那个x一定比当前最大值大…我们从x到INF二分即可,显然这是满足单调性的…

然而我因为INF开小了瞬间爆炸…

/********************************************
 
    Title       BZOJ2756.cpp
    Author      TomatoLoveCoconut
    Time        2018-3-29
    History     Created 2018-3-29
     
    Version     1.0.0
     
    Tags:       Flows
 
 
    while(true) RP++;
     
         QAQ
 
*********************************************/
 
 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF (1LL<<50)
#define base 311
#define mod 19270817
#define maxlongint 2147483647
#define maxint 32767
#define pi (double)acos(-1.0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
//SGT
#define MID (l+r)>>1
#define lson o<<1
#define rson o<<1|1
//clear the array
#define cla(a) memset(a,0,sizeof(a))
#define clb(a) memset(a,INF,sizeof(a));
#define clc(a) memset(a,-1,sizeof(a));
#define maxn 3000
#define P(x,y) (x-1)*m+y
 
using namespace std;
 
 
//complex
struct Complex{
    double x,y;
    Complex(double xx=0,double yy=0){x=xx,y=yy;}
};
inline Complex operator + (Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
inline Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
inline Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.y*b.x+b.y*a.x);}
//BIT
inline int lowbit(int x){return x&(-x);}
 
 
 
 
//var
struct Edge{
    int from,to;
    ll cap,flow;
};
struct Dinic{
    int vis[maxn];
    int d[maxn];
    int cur[maxn];
    vector<Edge> edges;
    vector<int> G[maxn];
    int n,s,t;
    void init(int n,int s,int t)
    {
        this->n=n;
        this->t=t;
        this->s=s;
        for (int i=0;i<=n;i++)
            G[i].clear();
        edges.clear();
    }
    void addedge(int from,int to,ll cap)
    {
        edges.push_back((Edge){from,to,cap,0});
        edges.push_back((Edge){to,from,0,0});
        int m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    bool BFS()
    {
        memset(d,0,sizeof(0));
        memset(vis,0,sizeof(vis));
        queue<int> q;
        q.push(s);
        vis[s]=1;
        d[s]=0;
        while (!q.empty())
        {
            int u=q.front();
            q.pop();
            for (int i=0;i<G[u].size();++i)
            {
                Edge &e=edges[G[u][i]];
                if (!vis[e.to] && e.cap>e.flow)
                {
                    q.push(e.to);
                    vis[e.to]=1;
                    d[e.to]=d[u]+1;
                }
            }
        }
        return vis[t];
    }
    ll DFS(int u,ll a)
    {
        if (u==t || a==0) return a;
        ll flow=0;
        ll f;
        for (int &i=cur[u];i<G[u].size();i++)
        {
            Edge &e=edges[G[u][i]];
            if (d[e.to]==d[u]+1 && (f=DFS(e.to,min(a,e.cap-e.flow)))>0)
            {
                e.flow+=f;
                edges[G[u][i]^1].flow-=f;
                flow+=f;
                a-=f;
            }
            if (a==0)  break;
        }
        return flow;
    }
    ll Maxflow()
    {
        ll flow=0;
        while (BFS())
        {
            memset(cur,0,sizeof(cur));
            flow+=DFS(s,INF);
        }
        return flow;
    }
}dinic;
             
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct BZOJ2756{
    int a[45][45];
    bool col[45][45];
    int n,m;
    inline bool check(ll x)
    {
        int S=n*m+1;
        int T=n*m+2;
        ll cnt=0;
        dinic.init(n*m+10,S,T);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
            {
                if (col[i][j])
                {
                    dinic.addedge(S,P(i,j),x-a[i][j]);
                    cnt+=x-a[i][j];
                 
                    for (int k=0;k<4;k++)
                    {
                        int X=i+dx[k];
                        int Y=j+dy[k];
                        if (X<1 || Y<1 || X>n || Y>m) continue;
                        dinic.addedge(P(i,j),P(X,Y),INF);
                    }
                }
                else
                {
                    dinic.addedge(P(i,j),T,x-a[i][j]);
                }
            }
        if (dinic.Maxflow()==cnt) 
            return 1;
        else
            return 0;
    }
    inline void  run()
    {
        ll B=0,W=0;
        int cb=0,cw=0;
        int mx=0;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                {
                    scanf("%d",&a[i][j]);
                    col[i][j]=(i+j)&1;
                    mx=max(mx,a[i][j]);
                    if (col[i][j]==1)
                    {
                        cb++;
                        B+=a[i][j];
                    }
                    else
                    {
                        cw++;
                        W+=a[i][j];
                    }
                }
        if (cb!=cw)
        {
            ll x=(B-W)/(cb-cw);
            if (x>=mx)
            {
                if (check(x))
                {
                    printf("%lld\n",x*cb-B);
                    return ;
                }
            }
            puts("-1");
        }
        else{
            if (B!=W)
            {
                puts("-1");
                return ;
            }
            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*cb-B);
        }
    }
}solve;
 
 
int main()
{
    //freopen("1.in","r",stdin);
    //freopen(".out","w",stdout);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        solve.run();
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注