BZOJ2502:清理雪道 上下界网络流

思路:

比较一眼.

长了一个姿势,就是有源汇有上下界网络最小流求法.

首先求可行流,得到满足下界需要的流量,就是从原来的汇流回原来的源的流量(\(C_1\)).

这不见得是最小的.

因此我们删去原来的源和原来的汇之间的边,再求一次从原来的汇到原来的源的最大流(\(C_2\)),也即退掉尽可能多的流量.

由于下界是不会退流的.

显而易见(?).\(C_1-C_2\)就是答案.

据称有时候这样做还会出问题?

大家一起来围观Kanari神犇:详细的~~~~网址如下:

http://blog.csdn.net/huzecong/article/details/8631748

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
 
#define INF 0x3f3f3f3f
 
int cnt;
struct MaxflowSolver{
    int head[110],next[80010],end[80010],flow[80010],ind;
    int d[110],gap[110],stk[110],top,cur[110];
    inline void reset(){ind=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[110];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 res=0,u=S,Min,ins,i;top=0,bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<cnt+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(flow[stk[i]]<Min)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){stk[top++]=cur[u]=ins,u=end[ins];}
            else{
                Min=cnt+1;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;
 
int main(){
    int n;scanf("%d",&n);
    register int i,j;
    cnt=n;int SS=0,ST=++cnt,S=++cnt,T=++cnt;
     
    int t,x;SteinsGate.reset();
    for(i=1;i<=n;++i){
        SteinsGate.make(S,i,INF);
        SteinsGate.make(i,T,INF);
        scanf("%d",&t);
        while(t--)scanf("%d",&x),SteinsGate.make(SS,x,1),SteinsGate.make(i,ST,1),SteinsGate.make(i,x,INF);
    }
    SteinsGate.make(T,S,INF);
     
    int res;
    SteinsGate.Maxflow(SS,ST);
    for(j=SteinsGate.head[S];j!=-1;j=SteinsGate.next[j])if(SteinsGate.end[j]==T)res=SteinsGate.flow[j],SteinsGate.flow[j]=SteinsGate.flow[j^1]=0;
    printf("%d",res-SteinsGate.Maxflow(T,S));
     
    return 0;
}