[SCOI2012]奇怪的游戏

Description:

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

Solution:

也算是网络流+二分答案的套路题吧
这个人讲得很好,转自

不难看出，对棋盘进行黑白染色之后，每次相加都会使得相邻的一黑一白两个格子同时+1,。
先对所有黑白格子进行统计，处理出\(cnt0\),\(cnt1\)分别代表黑、白格子个数，处理出\(sum0\),\(sum1\)分别代表黑、白格子权值和。
分类讨论如下：
如果\(cnt0=cnt1\)
　　如果\(sum0\not =sum1\)，那么一定不存在合法解
　　如果\(sum0=sum1\)，设最终所有数字都变成\(ans\)，发现如果\(ans\)满足，则\(ans+1\)必定也满足(补充:因为此时n,m中必有一个偶数,可以随意给所有数+1)，即\(ans\)满足二分性质，因此可以二分答案，网络流判断是否可行。
如果\(cnt0\not =cnt1\)
　　依旧设最终数字为\(ans\)，则有\(cnt0\times ans-sum0=cnt1\times ans-sum1\)，化简得\(ans=\frac{sum0-sum1}{cnt0-cnt1}\)，只需要检查这个值是否合法即可。

网络流判断可行的方法：
从S向每个黑点连\(ans-Val_{i,j}\)的边，从每个白点向T连\(ans-Val_{i,j}\)的边，相邻的黑点向白点连\(+\infty\)的边，判断是否满流。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const ll mxn=1e5+5,inf=1e17;
ll c0,c1,s0,s1,n,m,cnt,ans,hd[mxn];
ll a[55][55],col[55][55];
ll dx[5]={0,0,1,-1},dy[5]={1,-1,0,0};

inline ll read() {
    char c=getchar(); ll x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(ll &x,ll y) {if(xy) x=y;}

struct ed {
    ll to,nxt,w;
}t[mxn<<1];

inline void add(ll u,ll v,ll w) {
    t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
    t[++cnt]=(ed) {u,hd[v],0}; hd[v]=cnt;
}

ll S,T,cur[mxn],dep[mxn];

ll bfs() {
    memset(dep,0,sizeof(dep)); dep[S]=1;
    queue q; q.push(S); 
    for(ll i=S;i<=T;++i) cur[i]=hd[i];
    while(!q.empty()) {
        ll u=q.front(); q.pop();
        for(ll i=hd[u];i!=-1;i=t[i].nxt) {
            ll v=t[i].to;
            if(!dep[v]&&t[i].w>0) 
                dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[T];
}

ll dfs(ll u,ll f) {
    if(u==T) return f;
    for(ll &i=cur[u];i!=-1;i=t[i].nxt) {
        ll v=t[i].to;
        if(t[i].w>0&&dep[v]==dep[u]+1) {
            ll tp=dfs(v,min(f,t[i].w));
            if(tp>0) {
                t[i].w-=tp;
                t[i^1].w+=tp;
                return tp;
            }
        }
    }
    return 0;
} 

void Dinic() {
    while(bfs()) 
        while(ll tp=dfs(S,inf)) 
            ans+=tp;
}

ll get(ll x,ll y) {
    return (x-1)*m+y;
}

ll check(ll x) {
    memset(hd,-1,sizeof(hd));
    cnt=-1; S=ans=0; T=n*m+1; ll tot=0;
    for(ll i=1;i<=n;++i) 
        for(ll j=1;j<=m;++j)
            if(col[i][j]) {
                add(S,get(i,j),x-a[i][j]); 
                tot+=x-a[i][j];
                for(ll k=0;k<4;++k) {
                    ll tx=i+dx[k],ty=j+dy[k];
                    if(tx<1||ty<1||tx>n||ty>m) continue ;
                    add(get(i,j),get(tx,ty),inf);
                }
            }
            else add(get(i,j),T,x-a[i][j]);
    Dinic(); return ans==tot;
}

int main()
{
    ll T; T=read();
    while(T--) {
        c0=c1=s0=s1=0; ll mx=0;
        n=read(); m=read();
        for(ll i=1;i<=n;++i) 
            for(ll j=1;j<=m;++j) 
                a[i][j]=read(),col[i][j]=(i+j)&1,chkmax(mx,a[i][j]);
        for(ll i=1;i<=n;++i) 
            for(ll j=1;j<=m;++j) 
                if(col[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&&check(x)) printf("%lld\n",x*c1-s1);
            else puts("-1"); 
        }		
        else {
            if(s0!=s1) {
                puts("-1");
                continue ;
            }
            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",1ll*l*c1-s1);
        }
    }
    return 0;
}
网络流

相关

图论---网络流

网络流 学习笔记

Codeforces 1373F - Network Coverage（模拟网络流）

网络流24题-骑士共存

【网络流24题】最长不下降子序列问题

网络流各算法超详细带源码解析

python 方法无法在线程中使用（附python获取网络流量）

[教程]网络流详解: 从入门到放弃

网络流基础知识

网络流（二）

[知识点]网络流基础

【网络流】CF708D Incorrect Flow

标签