@zzzc18 2018-01-21T05:12:29.000000Z 字数 2950 阅读 997

# BZOJ2756: [SCOI2012]奇怪的游戏

bzoj 网络流

## Solution

$WhiteNum !=BlackNum$ 时直接判断 $X$ 是否可行，可行则输出解，否则无解
$WhiteNum==BlackNum$$X$ 是无意义的，也就是说算不出来

$S$ 到白点连容量为 $X-val[i][j]$ 的边，黑点到 $T$ 连容量为 $X-val[i][j]$ 的边，相邻的白点和黑点容量为INF
(脑补一下，白点和黑点都要加够 $X-val[i][j]$ 次，白点和黑点之间没有限制)

#include<queue>#include<cstdio>#include<cstring>#include<algorithm>#define LL long long#define MAXN 100#define MAXE 10000#define INF (1LL<<60)using namespace std;LL n,m;LL kase;LL num[MAXN][MAXN];LL color[MAXN][MAXN];struct E{    LL next,to,val;}edge[MAXE];LL head[MAXE],edge_num;LL depth[MAXE],iter[MAXE];queue<LL> que;LL s,t;LL cntw,cntb,sumw,sumb;LL u[5]={0,1,-1,0,0},v[5]={0,0,0,1,-1};LL FLOW;LL MAX;LL index(LL i,LL j){    return i*m+j;}bool inmap(LL x,LL y){    return x<=n && x>=1 && y<=m && y>=1;}void addedge(LL x,LL y,LL v){    edge[++edge_num].next=head[x];    edge[edge_num].to=y;    edge[edge_num].val=v;    head[x]=edge_num;}void INIT(){    scanf("%lld%lld",&n,&m);    s=m*(n+1)+1,t=m*(n+1)+2;    cntw=cntb=sumw=sumb=0;    LL i,j;    MAX=0;    for(i=1;i<=n;i++){        for(j=1;j<=m;j++){            scanf("%lld",&num[i][j]);            MAX=max(MAX,num[i][j]);            if((j%2)^(i%2))                color[i][j]=1,cntb++,sumb+=num[i][j];            else                color[i][j]=0,cntw++,sumw+=num[i][j];        }    }}void Graph(LL x){    LL i,j;    edge_num=1;    memset(head,0,sizeof(head));    FLOW=0;    for(i=1;i<=n;i++){        for(j=1;j<=m;j++){            if(color[i][j]==0){                FLOW+=x-num[i][j];                addedge(s,i*m+j,x-num[i][j]);                addedge(i*m+j,s,0);                LL k;                for(k=1;k<=4;k++){                    LL x,y;                    x=i+u[k],y=j+v[k];                    if(inmap(x,y)){                        addedge(index(i,j),index(x,y),INF);                        addedge(index(x,y),index(i,j),0);                    }                }            }            else{                addedge(i*m+j,t,x-num[i][j]);                addedge(t,i*m+j,0);            }        }    }}void BFS(){    memset(depth,-1,sizeof(depth));    que.push(s);    depth[s]=0;    LL i;    while(!que.empty()){        LL fro=que.front();que.pop();        for(i=head[fro];i;i=edge[i].next){            if(edge[i].val>0 && depth[edge[i].to]==-1){                depth[edge[i].to]=depth[fro]+1;                que.push(edge[i].to);            }        }    }}LL DFS(LL x,LL f){    if(x==t)        return f;    for(LL &i=iter[x];i;i=edge[i].next){        if(edge[i].val>0 && depth[edge[i].to]==depth[x]+1){            LL tmp=DFS(edge[i].to,min(f,edge[i].val));            if(tmp>0){                edge[i].val-=tmp;                edge[i^1].val+=tmp;                return tmp;            }        }    }    return 0;}LL Dinic(){    LL re=0;    while(true){        BFS();        if(depth[t]<0)            break;        LL tmp;        memcpy(iter,head,sizeof(head));        while(true){            tmp=DFS(s,INF);            if(tmp<=0){                break;            }            re+=tmp;        }    }    return re;}bool check(LL x){    return FLOW==x;}void PLAN1(){    LL x=(sumw-sumb)/(cntw-cntb);    if(x<MAX){        printf("-1\n");        return;    }    Graph(x);    LL tmp=Dinic();    if(check(tmp))        printf("%lld\n",x*cntw-sumw);    else        printf("-1\n");}void PLAN2(){    LL l,r;    l=MAX;r=(1LL<<50);    while(l<=r){        LL mid=(l+r)>>1;        Graph(mid);        LL tmp=Dinic();        if(check(tmp))            r=mid-1;        else            l=mid+1;    }    printf("%lld\n",l*cntw-sumw);}void solve(){    if(cntw!=cntb){        PLAN1();    }    else{        if(sumw!=sumb){            printf("-1\n");            return;        }        else            PLAN2();    }}int main(){    freopen("bzoj.in","r",stdin);    freopen("out.out","w",stdout);    scanf("%lld",&kase);    while(kase--){        INIT();        solve();    }    return 0;}

• 私有
• 公开
• 删除