BZOJ3577:玩手机 最大流+二维ST表优化

思路:

首先最大流显然,朴素建模显然.

但是边数是\(O((a+b)n^2)\)会爆炸.

因此我们得考虑优化.

注意到题目中的一个条件,也就是说每一个区域都是正方形.

因此我们设\(f[i][j][k]\)表示左上角坐标为\((i,j)\),边长为\(2^k\)的正方形区域,那么我们就可以用\(O(1)\)个这种正方形区域来完全覆盖所求的区域.

这样就可以过了.具体见代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
 
#define INF 0x3f3f3f3f
struct MaxflowSolver{
    static const int V=100000;
    static const int E=1000010;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],d[V],stk[V],top,cur[V];
    inline void reset(){ind=top=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;}
    inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T,int cnt){
        int i,Min,ins,u=S,res=0;bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j;break;}
            if(find)cur[u]=stk[top++]=ins,u=end[ins];
            else{
                Min=cnt;for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j;
                if(!--gap[d[u]])break;++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }return res;
    }
}Stg;
 
#define N 61
#define M 61
int in[N][M],out[N][M];
int left[N][M][6],right[N][M][6];
 
int len[61];
 
int main(){
    int n,m,a,b;scanf("%d%d%d%d",&n,&m,&a,&b);register int i,j,k;
    int cnt=0;
     
    Stg.reset();
    int S=++cnt,T=++cnt;
    int x;for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&x),Stg.make(in[i][j]=++cnt,out[i][j]=++cnt,x);
     
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)left[i][j][0]=++cnt,right[i][j][0]=++cnt;
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)Stg.make(left[i][j][0],in[i][j],INF);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)Stg.make(out[i][j],right[i][j][0],INF);
    for(k=1;(1<<k)<=n&&(1<<k)<=m;++k)for(i=1;i+(1<<k)-1<=n;++i)for(j=1;j+(1<<k)-1<=m;++j){
        left[i][j][k]=++cnt;
        Stg.make(left[i][j][k],left[i][j][k-1],INF);
        Stg.make(left[i][j][k],left[i+(1<<(k-1))][j][k-1],INF);
        Stg.make(left[i][j][k],left[i][j+(1<<(k-1))][k-1],INF);
        Stg.make(left[i][j][k],left[i+(1<<(k-1))][j+(1<<(k-1))][k-1],INF);
        right[i][j][k]=++cnt;
        Stg.make(right[i][j][k-1],right[i][j][k],INF);
        Stg.make(right[i+(1<<(k-1))][j][k-1],right[i][j][k],INF);
        Stg.make(right[i][j+(1<<(k-1))][k-1],right[i][j][k],INF);
        Stg.make(right[i+(1<<(k-1))][j+(1<<(k-1))][k-1],right[i][j][k],INF);
    }
     
    for(i=2;i<=60;++i)len[i]=len[i>>1]+1;
     
    int x1,y1,x2,y2,l;
    while(a--){
        scanf("%d%d%d%d%d",&x,&x1,&y1,&x2,&y2);l=len[x2-x1+1];
        Stg.make(S,++cnt,x);
        Stg.make(cnt,left[x1][y1][l],INF);
        Stg.make(cnt,left[x1][y2-(1<<l)+1][l],INF);
        Stg.make(cnt,left[x2-(1<<l)+1][y1][l],INF);
        Stg.make(cnt,left[x2-(1<<l)+1][y2-(1<<l)+1][l],INF);
    }
    while(b--){
        scanf("%d%d%d%d%d",&x,&x1,&y1,&x2,&y2);l=len[x2-x1+1];
        Stg.make(++cnt,T,x);
        Stg.make(right[x1][y1][l],cnt,INF);
        Stg.make(right[x1][y2-(1<<l)+1][l],cnt,INF);
        Stg.make(right[x2-(1<<l)+1][y1][l],cnt,INF);
        Stg.make(right[x2-(1<<l)+1][y2-(1<<l)+1][l],cnt,INF);
    }
     
    printf("%d",Stg.Maxflow(S,T,cnt));
     
    return 0;
}