上下界网络流即对边的流量有限制，必须在[down,up]的范围内。

无源汇有上下界可行流

模型：

一个网络，求出一个流，使得每条边的流量为，除了源点和汇点，每个点必须满足总流入量=总流出量（流量守恒）（这个流的特点是循环往复，无始无终）。

建图：

首先建立一个源ss和一个汇tt，一般称为附加源和附加汇。

对于图中的每条弧，假设它容量上界为c，下界b，那么把这条边拆为三条只有上界的弧。

一条为，容量为b；

一条为，容量为b；

一条为，容量为c−b。

其中前两条弧一般称为附加弧。

然后对这张图跑最大流，以ss为源，以tt为汇，如果所有的附加弧都满流，则原图有可行流。

这时，每条非附加弧的流量加上它的容量下界，就是原图中这条弧应该有的流量。

模板：

LOJ115

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

如果无解，输出一行NO。

否则第一行输出YES，之后m行每行一个整数，表示每条边的流量。

#define ll long long
const long long INF=0x3f3f3f3f3f3f3f3f;
int n;
int s,e;//源点、汇点
int top;
struct edge
{
    int to;
    ll cap;
    int next;
}eg[200010];//邻接表要开边数的两倍
int head[10010];
int cur[10010];//当前弧优化
int dis[10010];//分层图中每个点的层数（即到原点的最短距离）
void add(int x,int y,ll z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
ll dfs(int id,ll cp)
{
    if(id==e||cp==0)return cp;
    ll res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
ll dinic()
{
    ll ans=0;
    while(bfs())
    {
        for(int i=0;i<=n+1;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int m,x,y,l,r;
        scanf("%d%d",&n,&m);
        s=0;e=n+1;
        top=0;
        memset(head,-1,sizeof(head));
        while(m--)
        {
            scanf("%d%d%d%d",&x,&y,&l,&r);
            add(x,y,r-l);add(y,x,0);
            add(x,e,l);add(e,x,0);
            add(s,y,l);add(y,s,0);
        }
        dinic();
        bool sign=true;
        for(int i=head[s];i!=-1&&sign;i=eg[i].next)
            if(eg[i].cap!=0)sign=false;
        if(!sign)printf("NO\n");
        else
        {
            printf("YES\n");
            for(int i=1;i<top;i+=6)
                printf("%lld\n",eg[i].cap+eg[i+1].cap+eg[i+2].cap);
        }
    }
    return 0;
}

有源汇有上下界可行流

模型：

网络有一个源点s和汇点t，求出一个流使得源点的总流出量等于汇点的总流入量，其他的点满足流量守恒，而且每条边的流量满足上界和下界限制。

建图：

建立弧，容量下界为0，上界为∞。

然后对这个新图（实际上只是比原图多了一条边）按照无源汇可行流的方法建模，如果所有附加弧满流，则存在可行流。

求原图中每条边对应的实际流量的方法，同无源汇可行流，只是忽略掉弧就好。

而且这时候弧的流量就是原图的总流量。

有源汇有上下界最大流

模型：

网络有一个源点s和汇点t，求出一个流使得源点的总流出量等于汇点的总流入量，其他的点满足流量守恒,而且每条边的流量满足上界和下界限制。在这些前提下要求总流量最大。

建图：

首先按照有源汇可行流的方法建模。

如果存在可行流，那么在运行过有源汇可行流的图上（就是已经存在流量的那张图，流量不要清零），跑一遍从s到t的最大流（这里的s和t是原图的源和汇，不是附加源和附加汇），就是原图的最大流。

模板：

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

如果无解，输出一行 please go home to sleep。

否则输出最大流。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<unordered_set>
#include<bitset>
#include<map>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define ull unsigned long long
const long long INF=0x3f3f3f3f3f3f3f3f;
int n;
int s,e;//源点、汇点
int top;
struct edge
{
    int to;
    ll cap;
    int next;
}eg[200010];//邻接表要开边数的两倍
int head[10010];
int cur[10010];//当前弧优化
int dis[10010];//分层图中每个点的层数（即到原点的最短距离）
void add(int x,int y,ll z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
ll dfs(int id,ll cp)
{
    if(id==e||cp==0)return cp;
    ll res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
ll dinic()
{
    ll ans=0;
    while(bfs())//建立分层图
    {
        for(int i=0;i<=n+1;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    int m,x,y,l,r;
    int curs,cure;
    scanf("%d%d%d%d",&n,&m,&curs,&cure);
    s=0;e=n+1;
    top=0;
    memset(head,-1,sizeof(head));
    while(m--)
    {
        scanf("%d%d%d%d",&x,&y,&l,&r);
        add(x,y,r-l);add(y,x,0);
        add(x,e,l);add(e,x,0);
        add(s,y,l);add(y,s,0);
    }
    add(s,curs,INF);add(curs,s,0);
    add(cure,e,INF);add(e,cure,0);
    ll maxflow=dinic();
    bool sign=true;
    ll flow=0;
    for(int i=eg[head[s]].next;i!=-1&&sign;i=eg[i].next)
    {
        if(eg[i].cap!=0)sign=false;
        flow+=eg[i^1].cap;
    }
    if(!sign)printf("please go home to sleep\n");
    else printf("%lld\n",maxflow-flow);
    return 0;
}

有源汇有上下界最小流

模型：

模型:现在的网络有一个源点s和汇点t，求出一个流使得源点的总流出量等于汇点的总流入量，其他的点满足流量守恒，而且每条边的流量满足上界和下界限制。在这些前提下要求总流量最小。

建图：

首先按照有源汇可行流的方法建模，但是不要建立这条弧。

然后在这个图上，跑从附加源ss到附加汇tt的最大流。

这时候再添加弧，下界为0，上界为∞。

在现在的这张图上，从ss到tt的最大流，就是原图的最小流。

学习

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

构造 Previous
HDU5514 容斥原理/欧拉函数的应用 Next