前置知识

网络流求最大流的算法最少要会一种，安利一下我以前写的博客：
通俗易懂的网络流入门：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跑最大流，会将可行流这部分加上去。

有上下界的网络流问题