BZOJ2756: [SCOI2012]奇怪的游戏

bzoj 网络流

题就不再念了

Solution

首先对棋盘进行黑白染色，像这样

然后要统计白点个数，初始白点点权和以及黑点个数与初始黑点点权和
显然的是，最终得到的值 $X$ 可以写作

当 $WhiteNum !=BlackNum$ 时直接判断 $X$ 是否可行，可行则输出解，否则无解
当 $WhiteNum==BlackNum$ 时 $X$ 是无意义的，也就是说算不出来
但此时可以看出来，若 $X$ 可以满足题意 那么 $X+1$ 也满足题意(任意的白点都可以有一个与它配对的黑点一起 $+1$ ，整个图都这么做，$X+1$ 也就可以加出来)
说明了什么？可以二分了
二分 $X$ 可以求出

二分的 $Check()$ 要用到网络流
设源点为 $S$ 汇点为 $T$
$S$ 到白点连容量为 $X-val[i][j]$ 的边，黑点到 $T$ 连容量为 $X-val[i][j]$ 的边，相邻的白点和黑点容量为INF
(脑补一下，白点和黑点都要加够 $X-val[i][j]$ 次，白点和黑点之间没有限制)
如果这个图是满流的，说明 $X$ 可行，否则不可行

这题时限40s，似乎可以用来给不法分子卡评测

注意：long long还是很慢的，memset，memcpy很耗时，刚开始浪数组开太大，卡了一个40s的TLE。。。

#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;
}