BZOJ-2756: [SCOI2012]奇怪的游戏

[文章目录]

Description

这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻的格子,并使这两个数都加上 1。现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同一个数则输出-1。多组数据 T<=10,1<=N,M<=40 ai<=10^9

发现如果知道最后那个数(设为x)是什么的话,可以将行列构建二分图,跑残量网络,如果满流,则可行。
分类讨论:
如果n*m为偶数,如果最后相同的数大于x,都可行。可以二分答案,每次判定。
如果n*m为奇数,黑白染色,发现有一种多了一块。那么两个点集的差即为最后的x,直接判定即可。

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x3bbbbbbbbbbbbbbbll;
int n,m,s,t,T;
int mp[50][50];
int head[2000],nxt[20000],to[20000],cnt;
ll f[20000];
inline int id(int i,int j)
{
    if(i<1||i>n||j<1||j>m) return 0;
    return (i-1)*m+j;
}
inline void add(int x,int y,ll z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
    to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[2000];
bool bfs()
{
    while(!q.empty()) q.pop();
    memset(dis,-1,sizeof dis);
    dis[s]=0; q.push(s); int x,i;
    while(!q.empty())
    {
        x=q.front(); q.pop();
        for(i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
        {
            dis[to[i]]=dis[x]+1;
            if(to[i]==t) return true;
            q.push(to[i]);
        }
    }
    return false;
}
ll dinic(int x,ll flow)
{
    if(x==t) return flow;
    ll xx,tmp=flow;
    for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
    {
        xx=dinic(to[i],min(tmp,f[i]));
        if(!xx) dis[to[i]]=-1;
        f[i]-=xx; f[i^1]+=xx; tmp-=xx;
        if(!tmp) return flow;
    }
    return flow-tmp;
}
bool check(ll x)
{
    if(x<0) return false;
    memset(head,0,sizeof head); cnt=1;
    int i,j; ll ans=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
        {
            if(mp[i][j]>x) return false;
            if((i+j)&1)
            {
                add(s,id(i,j),x-mp[i][j]); ans+=x-mp[i][j];
                if(id(i-1,j)) add(id(i,j),id(i-1,j),inf);
                if(id(i,j-1)) add(id(i,j),id(i,j-1),inf);
                if(id(i+1,j)) add(id(i,j),id(i+1,j),inf);
                if(id(i,j+1)) add(id(i,j),id(i,j+1),inf);
            }
            else add(id(i,j),t,x-mp[i][j]);
        }
    while(bfs()) ans-=dinic(s,inf);
    return ans==0;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m); s=n*m+1; t=s+1;
        int i,j; ll s1=0,s2=0;
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j)
            {
                scanf("%d",&mp[i][j]);
                if((i+j)&1) s2+=mp[i][j];
                else s1+=mp[i][j];
            }
        if((n*m)&1)
        {
            if(check(s1-s2)) printf("%lld\n",(s1-s2)*(n*m/2)-s2);
            else puts("-1");
        }
        else
        {
            if(s1!=s2) {puts("-1"); continue;}
            ll l=0,r=0x7fffffff,mid;
            while(l<r)
            {
                mid=(l+r)>>1;
                if(check(mid)) r=mid;
                else l=mid+1;
            }
            if(r==0x7fffffff) puts("-1");
            else printf("%lld\n",r*(n*m/2)-s2);
        }
    }
    return 0;
}

发表评论

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