[BZOJ2756][SCOI2012]奇怪的游戏 二分答案+最大流


原题链接
给一张网格图,每个格子有一个初始值,一次操作可以将相邻的两个格子的值+1,现在希望最后让所有格子值相等,求最小操作次数.
显然:
1.只需求出最后所有格子的值是多少,就知道最小操作次数.
2.每次操作同时修改相邻两个格子,所以可以黑白染色,染色后黑点和白点的和的差是无法改变的.
对网格图黑白染色,设最终值是x,黑格子初始和为bsum,白格子为wsum,则有
也就是

接下来就好做了.
如果格子数是奇数,则x=bsum-wsum,用最大流判断一下是否可行;
如果格子数是偶数,首先看等式右边是不是0判断是否有解;同时,如果x可行,x+1也可行,因此满足二分性质,二分答案每次用最大流判断即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 23333
#define X 42
#define M 233333
using namespace std;
typedef long long ll;
const ll inf=0x3bbbbbbbbbbbbbbbll;
int T;
int w,h;
ll a[X][X],s1,s2;
int s,t,head[N],to[M],nxt[M],tot=1;
ll f[M];
inline void add(int x,int y,ll z)
{
    to[++tot]=y,nxt[tot]=head[x],head[x]=tot,f[tot]=z;
    to[++tot]=x,nxt[tot]=head[y],head[y]=tot,f[tot]=0;
}
inline void init()
{
    memset(head,0,sizeof head);
    tot=1;
}
int dis[N],q[N],l,r;
inline bool bfs()
{
    l=1,r=0;
    memset(dis,0,sizeof dis);
    dis[s]=1,q[++r]=s;
    int x,i,y;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=nxt[i])if(!dis[y=to[i]]&&f[i])
        {
            dis[y]=dis[x]+1;
            if(y==t)return 1;
            q[++r]=y;
        }
    }
    return 0;
}
ll dinic(int x,ll flow)
{
    if(x==t)return flow;
    ll tmp,lft=flow;
    for(int y,i=head[x];i;i=nxt[i])if(dis[y=to[i]]==dis[x]+1&&f[i])
    {
        tmp=dinic(y,min(f[i],lft));
        if(!tmp)dis[y]=0;
        lft-=tmp,f[i]-=tmp,f[i^1]+=tmp;
        if(!lft)return flow;
    }
    return flow-lft;
}
ll maxflow()
{
    ll re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
inline int p(int i,int j)
{
    return (i-1)*h+j;
}
inline bool check(ll ans)
{
    init();
    int i,j;
    ll re=0;
    for(i=1;i<=w;++i)
    {
        for(j=1;j<=h;++j)
        {
            if(ans-a[i][j]<0)return 0;
            if((i&1)!=(j&1))add(p(i,j),t,ans-a[i][j]);
            else
            {
                re+=ans-a[i][j];
                add(s,p(i,j),ans-a[i][j]);
                if(i>1)add(p(i,j),p(i-1,j),inf);
                if(j>1)add(p(i,j),p(i,j-1),inf);
                if(i<w)add(p(i,j),p(i+1,j),inf);
                if(j<h)add(p(i,j),p(i,j+1),inf);
            }
        }
    }
    ll tmp=maxflow();
    return tmp==re;
}
int main()
{
    cin>>T;
    int i,j;
    ll l,r,mid;
    while(T--)
    {
        scanf("%d%d",&w,&h);
        s=0,t=w*h+1;
        s1=s2=0;
        for(i=1;i<=w;++i)
        {
            for(j=1;j<=h;++j)
            {
                scanf("%lld",&a[i][j]);
                if((i&1)==(j&1))s1+=a[i][j];
                else s2+=a[i][j];
            }
        }
        if(w*h%2==1)
        {
            if(check(s1-s2))printf("%lld\n",((s1-s2)*w*h-s1-s2)/2);
            else puts("-1");
        }
        else
        {
            if(s1!=s2)
            {
                puts("-1");
                continue;
            }
            l=1,r=2147483647;
            while(l<r)
            {
                mid=(l+r)>>1;
                if(check(mid))r=mid;
                else l=mid+1;
            }
            printf("%lld\n",(r*w*h-s1-s2)/2);
        }
    }
    return 0;
}

发表评论

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