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

BZOJ3218:a + b Problem 网络流+线段树

思路:

首先最小割的建模是显然的.

令\(S\)集合表示选择白色,\(T\)集合表示选择黑色.

则有:

\[S->i~c=w_i\]表示割掉这条边之后,\(i\)在\(T\)集合,颜色为黑色,失去了白色的价值.

同理\[i->T~c=b_i\].

接下来假设有一堆点,若这些点有一个为白色,且\(i\)为黑色,则损失价值\(p_i\).

这个怎么搞?

设一个辅助节点\(x\),让所有对\(i\)有影响的点\(j\)都连\(j->x~c=INF\).然后再连接\(x->i~c=p_i\).

这样的话,如果有某个点\(x\)选了白色(属于\(S\)集),而节点\(i\)为黑色(属于\(T\)集),那么这条\(p_i\)的边就必定需要割掉.

 

可是这样边数爆表.

注意到一堆\(INF\)的边很是浪费,于是我们用线段树优化.

首先不考虑标号的限制,只考虑\(l\leq{a}\leq{r}\)的限制.

离散化后,我们用线段树上的\(O(logn)\)个节点来连向辅助节点.

 

接下来是标号的限制...

我们用一颗可持久化线段树来维护连边即可.

(关于可持久化线段树的姿势可以看代码)

(内附良心样例)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<map>
using namespace std;
  
#define INF 0x3f3f3f3f
  
#define N 5010
int a[N],b[N],w[N],l[N],r[N],p[N];
  
int seq[N*3],id;
  
struct MaxflowSolver{
    int head[300010],next[1000010],end[1000010],flow[1000010],ind;
    int d[300010],gap[300010],cur[300010],stk[300010],top;
    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){/*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);}
    inline void bfs(int T){
        static int q[300010];int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++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 res=0,i,Min,ins,u=S;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;
    }
}SteinsGate;
  
struct Node{
    int l,r;
}S[300010];int cnt;
  
int root[5010];
int Newversion(int last,int tl,int tr,int ins){
    int q=++cnt;S[q]=S[last];if(last)SteinsGate.make(last,q,INF);if(tl==tr)return q;
    int mid=(tl+tr)>>1;
    if(ins<=mid)S[q].l=Newversion(S[last].l,tl,mid,ins);else S[q].r=Newversion(S[last].r,mid+1,tr,ins);
    return q;
}
  
void Addedge(int q,int tl,int tr,int dl,int dr,int topoint){
    if(dl<=tl&&tr<=dr){if(q)SteinsGate.make(q,topoint,INF);return;}
    int mid=(tl+tr)>>1;
    if(dr<=mid)Addedge(S[q].l,tl,mid,dl,dr,topoint);
    else if(dl>mid)Addedge(S[q].r,mid+1,tr,dl,dr,topoint);
    else Addedge(S[q].l,tl,mid,dl,mid,topoint),Addedge(S[q].r,mid+1,tr,mid+1,dr,topoint);
}
  
int main(){
    int n;scanf("%d",&n);register int i,j;
    for(i=1;i<=n;++i)scanf("%d%d%d%d%d%d",&a[i],&b[i],&w[i],&l[i],&r[i],&p[i]);
  
    for(i=1;i<=n;++i)seq[++id]=a[i],seq[++id]=l[i],seq[++id]=r[i];sort(seq+1,seq+id+1);
    map<int,int>M;int num=0;for(seq[0]=-1<<30,i=1;i<=id;++i)if(seq[i]!=seq[i-1])M[seq[i]]=++num;
    for(i=1;i<=n;++i)a[i]=M[a[i]],l[i]=M[l[i]],r[i]=M[r[i]];
  
    SteinsGate.reset();
    for(i=1;i<=n;++i)root[i]=Newversion(root[i-1],1,num,a[i]),SteinsGate.make(250000+i,cnt,INF);
    for(i=1;i<=cnt;++i){
        if(S[i].l)SteinsGate.make(S[i].l,i,INF);
        if(S[i].r)SteinsGate.make(S[i].r,i,INF);
    }
  
    int S=0,T=++cnt,res=0;
    for(i=1;i<=n;++i)res+=b[i]+w[i],SteinsGate.make(S,250000+i,w[i]),SteinsGate.make(250000+i,T,b[i]);
    for(i=1;i<=n;++i)if(i)Addedge(root[i-1],1,num,l[i],r[i],++cnt),SteinsGate.make(cnt,250000+i,p[i]);
  
    printf("%d",res-SteinsGate.Maxflow(S,T,cnt+1+n));
  
#ifndef ONLINE_JUDGE
    system("pause");
#endif
  
    return 0;
}
/*10
0 1 7 3 9 2
7 4 0 9 10 5
1 0 4 2 10 2
7 9 1 5 7 2
6 3 5 3 6 2
6 6 4 1 8 1
6 1 6 0 6 5
2 2 5 0 9 3
5 1 3 0 2 5
5 6 7 1 1 2*/

 

BZOJ3442:学习小组 费用流

思路:

一开始YY了一个上下界最小费用流,结果有负圈...看来只有消圈姿势对才能搞了.

其实只有一个问题就是如何用最大流来限制参加的人数尽可能多,我们可以连接:

\[S->i~Maxcap=k~Cost=0\]

\[i->T~Maxcap=k-1~Cost=0\]

这样就确保了最大流中每个人必定会走\(1\)的流量.

剩下的就水了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x3f3f3f3f
 
int cnt;
struct CostFlowSolver{
    int head[210],next[2000010],end[2000010],flow[2000010],cost[2000010],ind;
    int d[210],ld[210],lb[210];bool inq[210];queue<int>q;
    inline void reset(){ind=0,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q]=c;}
    inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);}
    inline bool spfa(int S,int T){
        memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S);
        while(!q.empty()){
            int i=q.front();q.pop(),inq[i]=0;for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                d[end[j]]=d[i]+cost[j],ld[end[j]]=i,lb[end[j]]=j;if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }return d[T]!=INF;
    }
    inline int Mincost(int S,int T){
        int res=0,Min,i;
        while(spfa(S,T)){for(Min=INF,i=T;i^S;i=ld[i])Min=min(Min,flow[lb[i]]);for(i=T;i^S;i=ld[i])flow[lb[i]]-=Min,flow[lb[i]^1]+=Min;res+=Min*d[T];}
        return res;
    }
}SteinsGate;
 
int c[110],f[110];
int main(){
    int n,m,k;scanf("%d%d%d",&n,&m,&k);register int i,j;
    for(i=1;i<=m;++i)scanf("%d",&c[i]);for(i=1;i<=m;++i)scanf("%d",&f[i]);
 
    cnt=n+m;int S=0,T=++cnt;
    SteinsGate.reset();
    for(i=1;i<=n;++i)SteinsGate.make(S,i,k,0);
    for(i=1;i<=n;++i)if(k>1)SteinsGate.make(i,T,k-1,0);
    int x;for(i=1;i<=n;++i)for(j=1;j<=m;++j){scanf("%1d",&x);if(x)SteinsGate.make(i,n+j,1,-f[j]);}
    for(j=1;j<=m;++j)for(i=1;i<=n;++i)SteinsGate.make(n+j,T,1,c[j]*(2*i-1));
 
    printf("%d",SteinsGate.Mincost(S,T));
    return 0;
}

BZOJ3876:[Ahoi2014]支线剧情 有上下界网络流

思路:

首先建立有上下界的网络流模型:

\[S->1~cap=[0,INF]~cost=0\]

\[i->T~cap=[0,INF]~cost=0(1\leq{i}\leq{n})\]

\[x->y~cap=[1,INF]~cost=w_{x->y}(ForEach x->y)\]

显然是有源汇的上下界网络流模型,我们对下界不为0的边拆边变成只有上界的网络流模型:

设立附加源\(SS\),附加汇\(\ST),则对于:

\[a->b~cap=[l,r]~cost=w_{a->b}\]

我们这样转化:

(1)\[SS->b~Maxcap=l~cost=w_{a->b}\]

(2)\[a->ST~Maxcap=l~cost=0\]

(3)\[a->b~Maxcap=r-l~cost=w_{a->b}\]

注意:(1)(2)中只有一种边的费用为原来费用,另一种边的费用为0.(至于为什么这样连先挖坑)

我们还需要连:

\[T->S~Maxcap=INF~cost=0\]

然后就可以用最小费用最大流水过了.(有时间试试单纯形)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x3f3f3f3f
 
int cnt;
queue<int>q;
struct Solver{
    int head[5100],next[50010],end[50010],flow[50010],cost[50010],ind;
    int d[5100],used[5100],slack[5100],id;bool inq[5100];
    inline void reset(){ind=0,id=1,memset(head,-1,sizeof head);}
    inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q++]=c;}
    inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);}
    inline void spfa(int S,int T){
        memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S);
        while(!q.empty()){
            int i=q.front();q.pop(),inq[i]=0;
            for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){
                d[end[j]]=d[i]+cost[j];
                if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }for(int i=0;i<=cnt;++i)d[i]=d[T]-d[i];
    }
    inline bool Newlabel(){
        int Min=INF;for(int i=0;i<=cnt;++i)if(used[i]!=id&&slack[i]<Min)Min=slack[i];
        if(Min==INF)return 0;
        for(int i=0;i<=cnt;++i)if(used[i]==id)used[i]=-1,d[i]+=Min;return 1;
    }
    int Getflow(int p,int T,int maxflow){
        if(p==T)return maxflow;
        used[p]=id;
        for(int j=head[p];j!=-1;j=next[j]){
            if(flow[j]&&used[end[j]]!=id&&d[end[j]]+cost[j]==d[p]){
                int to=Getflow(end[j],T,maxflow<flow[j]?maxflow:flow[j]);if(to){flow[j]-=to,flow[j^1]+=to;return to;}
            }else if(flow[j])slack[end[j]]=min(slack[end[j]],d[end[j]]+cost[j]-d[p]);
        }return 0;
    }
    int Mincost(int S,int T){
        int res(0),get;spfa(S,T);
        do{
            memset(slack,0x3f,sizeof slack);
            while((get=Getflow(S,T,INF)))res+=d[S]*get,++id;
        }
        while(Newlabel());
        return res;
    }
}SteinsGate;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
 
    int n;scanf("%d",&n);
    cnt=n;int SS=0,ST=++cnt,S=++cnt,T=++cnt;
    SteinsGate.reset();
 
    int t,a,c;register int i,j;
    SteinsGate.make(S,1,INF,0);
    for(i=1;i<=n;++i){
        SteinsGate.make(i,T,INF,0);
        scanf("%d",&t);
        while(t--)scanf("%d%d",&a,&c),SteinsGate.make(SS,a,1,c),SteinsGate.make(i,ST,1,0),SteinsGate.make(i,a,INF,c);
    }
    SteinsGate.make(T,S,INF,0);
 
    printf("%d",SteinsGate.Mincost(SS,ST));
 
    return 0;
}