有上下界的网络流问题

出题人说这是最简单的题

https://ac.nowcoder.com/acm/problem/25875

前置知识

网络流求最大流的算法最少要会一种,安利一下我以前写的博客:
通俗易懂的网络流入门:EK
简单高效的Dinic算法
稍微复杂但效率很高的HLPP和ISAP算法
建议按顺序学习,并至少学完Dinic,因为Dinic不难,并且高效

无源汇的有上下界的可行流

名词解释

无源汇:不区分起点和终点的闭合图
有上下界:每条边都有一个流量上界和流量下界
可行流:此处仅考虑是否存在可行方案

解法

因为要跑网络流,所以我们引入一个起点ss和一个终点tt,接下来,考虑如何加边:
对于原图中每条边{s,t,low,up}(分别表示起点,终点,下界,上界),我们在网络流图中加入一条边{s,t,up-low}(分别表示起点,终点,边权)
对于每个点i,定义它的流量d[i]:流入的流量下界—流出的流量下界。
对于一个点i,如果d[i]>0(流入的流量多于流出的流量),则加边{ss,i,d[i]}(从ss补足缺失的部分),否则,加边{i,tt,-d[i]}(把多余的部分抽到tt)
然后从ss到tt跑最大流,如果此时能满流(从ss流出的边全部满流),则证明由于引入了额外边(上界-下界得到的边)能够使得每个点满足流入等于流出,故此时存在可行流

有源汇的有上下界的可行流

与无源汇的区别

由于原图有源s和汇t,我们只需加入一条边{t,s,0,inf}问题就转化为了无源汇的可行流

有源汇的有上下界的最大流

与可行流的区别

从ss到tt跑最大流的过程中,我们就求出了可行流,此时所有的边都已满足下界的要求,我们只需要从s到t跑一遍最大流即可在此基础上得到有源汇有上下界的最大流

完整代码(此题的)

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x; 
}
const int mx=1e6;
const int inf=1<<30;
int n,m;
int s,t,ss,tt;
int top=1;
int head[mx];
int cur[mx];
struct Edge{
    int v;
    int val;
    int next;
}edge[mx<<1];
void addedge(int u,int v,int val){
    edge[++top].v=v;
    edge[top].val=val;
    edge[top].next=head[u];
    head[u]=top;
}
void add(int u,int v,int val){
    addedge(u,v,val);
    addedge(v,u,0);
}
bool inque[mx];
int deep[mx];
bool spfa(int s,int t){
    for(int i=1;i<=n+2;++i)deep[i]=inf,cur[i]=head[i];
    queue<int>q;
    q.push(s);
    deep[s]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inque[u]=0;
        for(int i=head[u];i;i=edge[i].next){
            if(!edge[i].val)continue;
            int v=edge[i].v;
            if(deep[v]>deep[u]+1){
                deep[v]=deep[u]+1;
                if(!inque[v]&&v!=t){
                    q.push(v);
                    inque[v]=1;
                }
            }
        }
    }
    return deep[t]!=inf;
} 
int dfs(int flow,int u,int t){
    if(u==t)return flow;
    int used=0;
    for(int i=cur[u];i;i=edge[i].next){
        cur[u]=i;
        if(!edge[i].val)continue;
        int v=edge[i].v;
        if(deep[v]==deep[u]+1){
            int now=dfs(min(edge[i].val,flow-used),v,t);
            used+=now;
            edge[i].val-=now;
            edge[i^1].val+=now;
            if(used==flow)return flow;
        }
    }
    return used;
}
int Dinic(int s,int t){
    int maxflow=0;
    while(spfa(s,t)){
        maxflow+=dfs(inf,s,t);
    }
    return maxflow;
}
int d[mx];//每个点的流量(最小入流量-最小出流量) 
int main(){
    n=Read(),m=Read(),s=Read(),t=Read();
    ss=n+1,tt=n+2;//新的起点和终点 
    add(t,s,inf);//形成无源汇的图
    for(int i=1;i<=m;++i){
        int u=Read(),v=Read(),low=Read(),up=Read();
        add(u,v,up-low);//建多余部分的流量的图
        d[u]-=low;
        d[v]+=low; 
    } 
    int flow=0;//满流应该的流量 
    for(int i=1;i<=n;++i){
        if(d[i]>0)add(ss,i,d[i]),flow+=d[i];//少的量由起点补足  
        else add(i,tt,-d[i]);//多出来的量流给终点
    }
    int k=Dinic(ss,tt);
    if(k!=flow){//不可行 
        printf("please go home to sleep");
        return 0;
    }
    printf("%d",Dinic(s,t));
    return 0;
}

疑问

看完上述代码,你或许会疑惑:为什么跑过一遍从ss到tt的最大流之后再跑从s到t的最大流,答案不会丢失可行流的那部分,而网上许多博客也说要把t到s的边删掉,然后跑s到t的最大流,再加上t到s的边的权值
但是,实际上没有必要,因为你跑过一遍ss到tt的最大流之后,原来的边的可行流都跑到了t到s这条边的反向边上,此时从s到t跑最大流,会将可行流这部分加上去。

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 00:27
中南大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议