(模板)有上下界的网络流 总结

无源汇可行流

建图方法

将有上下界的网络流图转化成普通的网络流图 首先建立附加源点ss和附加汇点tt 对于原图中的边x->y,若限制为[b,c],那么连边x->y,流量为c-b 对于原图中的某一个点i,记d(i)为流入这个点的所有边的下界和减去流出这个点的所有边的下界和 (上面在连每一条边的时候建一个cur数组记一下输入输出即可) 若d(i)>0,那么连边ss->i,流量为d(i) ,同时期望的流量值sum+=d(i) 若d(i)<0,那么连边i->tt,流量为-d(i) 求解方法 在新图上跑ss到tt的最大流 若新图满流(流量等于sum),那么一定存在一种可行流 此时,原图中每一条边的流量应为新图中对应的边的流量+这条边的流量下界

EX:LOJ115

这是一道模板题。 n个点,m条边,每条边 e有一个流量下界 $lower(e) $ 和流量上界 $upper(e)$,求一种可行方案使得在所有点满足流量平衡条件的前提下,所有边满足流量限制。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
struct edge{
    int to,cap,rev,id;
};
vector<edge>G[310];
int level[305],iter[305],cur[305],lower[30500];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
int maxflow(int s,int t){
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(s,t,0x7f7f7f7f))
            flow+=f;
    }
}
struct ans{
    int id,flow;
    bool operator<(const ans&a)const{
        return id<a.id;
    }
};
int main()
{
    int n,m,i,j,k;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        int s,t,l,u;
        scanf("%d%d%d%d",&s,&t,&lower[i],&u);
        cur[s]-=lower[i];cur[t]+=lower[i];
        addedge(s,t,u-lower[i]);G[s].back().id=i;
    }
    int sum=0;
    for(i=1;i<=n;i++){
        if(cur[i]>0){
            addedge(0,i,cur[i]);
            sum+=cur[i];
        }
        else if(cur[i]<0){
            addedge(i,250,-cur[i]);
        }
    }
    int flow=maxflow(0,250);
    if(flow!=sum){
        cout<<"NO"<<endl;return 0;
    }
    vector<ans>as;
    for(i=1;i<=n;i++){
        for(auto a:G[i]){
            if(!a.id)continue;
            as.push_back(ans{a.id,lower[a.id]+G[a.to][a.rev].cap});
        }
    }
    sort(as.begin(),as.end());
    cout<<"YES"<<endl;
    for(auto a:as){
        cout<<a.flow<<endl;
    }

    return 0;
}

有源汇可行流

建图方法

在原图中添加一条边t->s,流量为inf 即让源点和汇点也满足流量平衡条件 这样就改造成了无源汇的网络流图,其余建图方法与无源汇可行流相同。

有源汇有上下界最大流

建图方法

将有上下界的网络流图转化成普通的网络流图 首先建立附加源点ss和附加汇点tt 对于原图中的边x->y,若限制为[b,c],那么连边x->y,流量为c-b 对于原图中的某一个点i,记d(i)为流入这个点的所有边的下界和减去流出这个点的所有边的下界和 若d(i)>0,那么连边ss->i,流量为d(i) 若d(i)<0,那么连边i->tt,流量为-d(i) (以上与无源汇可行流相同) 在原图中添加一条边t->s,流量为inf 即让源点和汇点也满足流量平衡条件 这样就改造成了无源汇的网络流图 (以上与有源汇可行流相同) 在新图上跑ss到tt的最大流 若新图满流,那么一定存在一种可行流 记此时$∑f(s,i)=sum1$ ,即此时t->s的最大流,也就是求反向边s->t的流量 将t->s这条边拆掉,在新图上跑s到t的最大流 记此时$∑f(s,i)=sum2 $,即maxflow(s,t) 最终答案即为sum1+sum2

EX:LOJ116

这是一道模板题。 n个点,m条边,每条边 e有一个流量下界$ lower(e) $和流量上界 $upper(e) $,给定源点 s与汇点 t,求源点到汇点的最大流。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct edge{
    int to,cap,rev;
    bool tag;
};
vector<edge>G[410];
int level[405],iter[405],cur[405],lower[10005];
void addedge(int from,int to,int cap,int s)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
    if(from==s)G[from].back().tag=true;
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
int maxflow(int s,int t){
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(s,t,0x7f7f7f7f))
            flow+=f;
    }
}
int main()
{
    int n,m,s,t,i,j,k;
    cin>>n>>m>>s>>t;
    for(i=1;i<=m;i++){
        int from,t,up;
        scanf("%d%d%d%d",&from,&t,&lower[i],&up);
        addedge(from,t,up-lower[i],s);cur[from]-=lower[i];cur[t]+=lower[i];
    }
    int sum=0;
    for(i=1;i<=n;i++){
        if(cur[i]>0){
            addedge(0,i,cur[i],s);sum+=cur[i];
        }
        else{
            addedge(i,250,-cur[i],s);
        }
    }
    addedge(t,s,(1<<31)-1,s);
    int flow=maxflow(0,250);
    if(sum!=flow){
        cout<<"please go home to sleep"<<endl;return 0;
    }
    int ans=G[s].back().cap;
    G[s].pop_back();G[t].pop_back();
    ans+=maxflow(s,t);
    cout<<ans<<endl;

    return 0;
}

有源汇有上下界最小流

建图方法

将有上下界的网络流图转化成普通的网络流图 首先建立附加源点ss和附加汇点tt 对于原图中的边x->y,若限制为[b,c],那么连边x->y,流量为c-b 对于原图中的某一个点i,记d(i)为流入这个点的所有边的下界和减去流出这个点的所有边的下界和 若d(i)>0,那么连边ss->i,流量为d(i) 若d(i)<0,那么连边i->tt,流量为-d(i) (以上与无源汇可行流相同) 求res=ss->tt最大流 连边t->s,inf 求res+=ss->tt最大流 如果res!=sum也就是期望中的满流,那么就没有可行解。 需要格外注意最小流判断是否有可行解的位置与时机与另外几种上下界网络流的不同!!! 否则,输出G[s].back().cap也就是从t到s inf边的实际流量,即为所求。

EX:LOJ117

n 个点,m条边,每条边 e有一个流量下界 $lower(e) $和流量上界 $upper(e)$,给定源点 s与汇点 t,求源点到汇点的最小流。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
struct edge{
    int to;ll cap;int rev;
};
vector<edge>G[50210];
int level[50205],iter[50205],low[125050];ll cur[50205];
void addedge(int from,int to,ll cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
ll dfs(int v,int t,ll f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            ll d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
ll maxflow(int s,int t){
    ll flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        ll f;
        while(f=dfs(s,t,0x7f7f7f7f7f7f7f7f))
            flow+=f;
    }
}
int main()
{
    int n,m,s,t,i,j,k;
    cin>>n>>m>>s>>t;
    for(i=1;i<=m;i++){
        int from,to,up;scanf("%d%d%d%d",&from,&to,&low[i],&up);
        cur[from]-=low[i];cur[to]+=low[i];addedge(from,to,up-low[i]);
    }
    ll sum=0;
    for(i=1;i<=n;i++){
        if(cur[i]>0){
            addedge(0,i,cur[i]);sum+=cur[i];
        }
        else if(cur[i]<0){
            addedge(i,50050,-cur[i]);
        }
    }
    ll flow=maxflow(0,50050);
    addedge(t,s,(1LL<<63)-1);
    flow+=maxflow(0,50050);
    if(flow!=sum){
        cout<<"please go home to sleep"<<endl;return 0;
    }
    cout<<G[s].back().cap<<endl;

    return 0;
}