P4843 清理雪道（上下界网络流）

P4843 清理雪道

上下界最小流

我们先搞一遍上下界可行流（转）

回忆上下界最大流的写法：在可行流的残量网络$s\ -\ t$上跑最大流，答案为可行流$+$残量网络的最大流

那么上下界最小流的写法呢？

只要在残量网络$t\ -\ s$上跑最大流，答案就是可行流$-$残量网络$t\ -\ s$的最大流辣

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define N 1005

#define M 1000005

const int inf=2e9;

int n,S,T,pS,pT,ex[N],d[N],cur[N];

queue <int> h; bool vis[N];

int cnt=,hd[N],nxt[M],ed[N],poi[M],val[M],fr[M];

inline void adde(int x,int y,int v){

    nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt,

    ed[x]=cnt, poi[cnt]=y, val[cnt]=v, fr[cnt]=x;

}

inline void link(int x,int y,int v){adde(x,y,v),adde(y,x,);}

inline void ins(int x,int y,int l,int r){link(x,y,r-l),ex[x]-=l,ex[y]+=l;}

bool bfs(){

    for(int i=;i<=pT;++i) vis[i]=,cur[i]=hd[i];

    h.push(S); vis[S]=;

    while(!h.empty()){

        int x=h.front(); h.pop();

        for(int i=hd[x];i;i=nxt[i]){

            int to=poi[i];

            if(!vis[to]&&val[i]>)

                d[to]=d[x]+,vis[to]=,h.push(to);

        }

    }return vis[T];

}

int dfs(int x,int a){

    if(x==T||a==) return a;

    int F=,f;

    for(int &i=cur[x];i;i=nxt[i]){

        int to=poi[i];

        if(d[to]==d[x]+&&(f=dfs(to,min(a,val[i])))>)

            a-=f,F+=f,val[i]-=f,val[i^]+=f;

        if(!a) break;

    }return F;

}

int dinic(){int re=; while(bfs())re+=dfs(S,inf);return re;}

void del(int x){for(int i=hd[x];i;i=nxt[i])val[i]=val[i^]=;}

int main(){

    scanf("%d",&n); int tt,pi;

    S=n+; T=S+; pS=T+; pT=pS+;

    for(int i=;i<=n;++i){

        ins(S,i,,inf);

        ins(i,T,,inf);

        scanf("%d",&tt);

        while(tt--) scanf("%d",&pi),ins(i,pi,,inf);

    }

    for(int i=;i<=T;++i){//调整

        if(ex[i]<) link(i,pT,-ex[i]);

        if(ex[i]>) link(pS,i,ex[i]);

    }link(T,S,inf);//T向S连inf，使流量守恒

    int tmps=S,tmpt=T;

    S=pS; T=pT; dinic();

    int Flow=val[cnt]; val[cnt]=val[cnt-]=;//可行流的大小即为(T,S,inf)的反向边的流量

    S=tmpt; T=tmps; del(pS); del(pT);//倒着跑最大流

    printf("%d",Flow-dinic());

    return ;

}