上下界网络流学习笔记

图论 学习笔记

无源汇上下界可行流

我们考虑一个问题：在一张图中，每条边有流量下界和流量上界，求是否存在一种方案在满足流量平衡的情况下，使所有边满足上下界限制。

注意：这里的流量平衡指：对于所有点$x$，满足$\forall_{e\in E,e.to==x}e.flow=\forall_{e'\in E,e'.from==x}e'.flow$（$e.from$与$e.to$分别为一条边的两个点，$e.flow$为这条边实际的流量），即对于每个点都满足流入它的流量等于流出它的流量。

很容易想到一种想法，我们把上限减去下限，然后跑最大流。但是这个很显然是不满足的，因为经过操作后可能会形成这样的图：，这张图是很显然没有可行流的。但是经过操作后，原图会变为：，此时存在可行流。

我们发现答案前后不一的原因是经过这种操作后新图不满足流量平衡了，这就很麻烦了，跑不了最大流，而且也不能随便发明一个不需要流量平衡的最大流算法，因此我们想想如何经过玄学操作是新图满足流量平衡。

对了！原点和汇点还在旁边晾着，我们要让它们干活。因为最大流算法中源点和汇点可以不满足流量平衡，因此我们可以把锅推到源点和汇点上，同样是把每条边上限减去下限，但是对于每个点，我们计算$in_x=\forall_{e\in E,e.to==x}e.flow$，$out_x=\forall_{e\in E,e.from==x}e.flow$，为了满足流量平衡，$x$可以获得的流量肯定是$min(in_x,out_x)$，此时不满足流量平衡的地方就是$\left|in_x-out_x\right|$了。因此，对于所有的$in_x>out_x$，我们从$s$向$x$连一条上限为$in_x-out_x$的边来补齐由于流量平衡损失的流量；对于所有的$in_x==out_x$，可以连边可以不连边；对于所有的$in_x<out_x$，我们从$x$向$t$连一条上限为$out_x-in_x$的边补齐由于流量平衡损失的流量。

简单来说，所有连向$x$的边抬高了$x$一共$in_x$的下限，所有从$x$连出的边抬高了$x$一共$out_x$的下限。为了让$x$连入和连出处于同一个水平，我们需要用可以不满足流量平衡的$s$和$t$抬高或降低$x$的下限（等于从连入经过一次抬高/降低再连出），这样可以让$x$处于流量平衡的状态。

因此，这个步骤已经很明了了：
1. 统计每个点$x$的$in_x$与$out_x$，即连向$x$的边的流量之和与连出$x$的边的流量之和。
2. 对于每一条原图里的边，流量设为上限减去下限，因此得到一张新图。
3. 虚拟源点与汇点$s$和$t$，对于所有的$x$，如果$in_x>out_x$，则从$s$向$x$连一条$in_x-out_x$的边，否则从$x$向$t$连一条$out_x-in_x$的边。
4. 跑一遍从$s$到$t$的最大流，如果$s$连出的边可以满流（由于流量平衡，等价于连向$t$的边可以满流），证明存在可行流。
代码：

#include<stdio.h>
#include<queue>
#define inf 1000000000
using namespace std;
const int maxn=205,maxm=200005;
int i,j,k,m,n,s,t,e,flg,ans,sum;
int start[maxn],to[maxm],then[maxm],worth[maxm],rev[maxm],dep[maxn],vis[maxn],in[maxn],out[maxn],low[maxm];
queue<int>q;
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y,int z,int r){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z,rev[e]=r;
}
inline void addedge(int x,int y,int z){
    add(x,y,z,e+2),add(y,x,0,e);
}
void bfs(){
    while(!q.empty())
        q.pop();
    for(int i=1;i<maxn;i++)
        dep[i]=inf,vis[i]=0;
    dep[s]=0;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=start[x];i;i=then[i]){
            int y=to[i];
            if(worth[i]&&dep[y]>dep[x]+1){
                dep[y]=dep[x]+1;
                if(vis[y]==0){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
int dfs(int x,int flw){
    if(x==t){
        flg=1,ans+=flw;
        return flw;
    }
    int rest=flw;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(worth[i]&&dep[y]==dep[x]+1){
            int newflw=dfs(y,min(rest,worth[i]));
            if(newflw>0){
                rest-=newflw;
                worth[i]-=newflw,worth[rev[i]]+=newflw;
                if(rest==0)
                    break;
            }
            else dep[y]=0;
        }
    }
    return flw-rest;
}
int Dinic(){
    ans=0;
    while(1){
        bfs();
        if(dep[t]==inf)
            break;
        flg=1;
        while(flg){
            flg=0;
            dfs(s,inf);
        }
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    s=n+1,t=n+2;
    for(i=1;i<=m;i++){
        int x,y,p,q;
        scanf("%d%d%d%d",&x,&y,&p,&q);
        low[i]=p,in[y]+=p,out[x]+=p;
        addedge(x,y,q-p);
    }
    for(i=1;i<=n;i++){
        if(in[i]>out[i])
            addedge(s,i,in[i]-out[i]),sum+=in[i]-out[i];
        else addedge(i,t,out[i]-in[i]);
    }
    if(Dinic()!=sum){
        puts("NO");
        return 0;
    }
    puts("YES");
    for(i=1;i<=m;i++)
        printf("%d\n",low[i]+worth[i*2]);
    return 0;
}

有源汇上下界可行流

考虑有源点和汇点的上下界可行流，即在无源汇上下界可行流的基础上增加两个点不满足流量守恒。

由于流量平衡流出$s$的流量很显然与流入$t$的流量是相等的，那么我们很容易发现只要连接一条$(t,s,inf)$的边，原图就可以转化为无源汇上下界可行流的裸题了！

因此，步骤为：
1. 从原图中的汇点向源点连一条上限为$inf$的边。
2. 跑一遍无源汇上下界可行流。
因为有源汇上下界可行流与无源汇上下界可行流极为相似，故不给代码。

有源汇上下界最大流

接下来，我们看有源汇的上下界最大流。我们并不满足于求可行流，在找可行流的基础上，还想找最大流，这样应该怎么办呢？

我们先找到一个可行流$flow1$，此时我们“榨干”了连接虚拟源点和虚拟汇点的边，因此我们不能再跑一遍从虚拟源点到虚拟汇点的最大流，因为这根本没有意义。

但是这个可行流不一定是最大流，因为可行流只会跑满与虚拟源点和虚拟汇点相连的边，因此$flow1$最多就是这些边的上限和，此时在原图中可能会有边是跑不满的。

因此我们考虑计算$flow2$为$flow1$还能向上浮动的流量（这里需要感性理解），那么如何求$flow2$呢？其实向上浮动某些流量可以等价于在原图中跑出增广路（很显然，因为每跑出一个增广路就会让答案$+1$），因此我们跑一遍从原图中的源点到原图中的汇点的最大流，并设其答案为$flow2$。

此时$ans=flow1+flow2$。

注意一点，在跑原图的最大流时需要删去从原图汇点到原图源点的边，如果这条边没有删去，则会导致$flow2$包含$flow1$（这也是另一种有源汇上下界最大流的求法，也就是在求可行流之后不删边直接跑最大流，此时答案就是这次最大流的结果）。

但是与虚拟源点和虚拟汇点相连的边可以不删去，因为在求第一次最大流的时候就已经将这些边“榨干”了（因为存在可行流的条件是满流）。

步骤：
1. 跑出一个有源汇上下界可行流，如果满流则设其答案为$flow1$，否则不存在答案。
2. 删去从原图汇点到原图源点的边。
3. 跑从原图源点到原图汇点的最大流，设答案为$flow2$，则总答案$ans=flow1+flow2$。

代码：

#include<stdio.h>
#include<queue>
#define inf 1000000000
using namespace std;
const int maxn=205,maxm=200005;
int i,j,k,m,n,s,t,s1,t1,s2,t2,e,flg,ans,sum,anss;
int start[maxn],to[maxm],then[maxm],worth[maxm],rev[maxm],dep[maxn],vis[maxn],in[maxn],out[maxn];
queue<int>q;
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y,int z,int r){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z,rev[e]=r;
}
inline void addedge(int x,int y,int z){
    add(x,y,z,e+2),add(y,x,0,e);
}
void bfs(){
    while(!q.empty())
        q.pop();
    for(int i=1;i<maxn;i++)
        dep[i]=inf,vis[i]=0;
    dep[s]=0;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=start[x];i;i=then[i]){
            int y=to[i];
            if(worth[i]&&dep[y]>dep[x]+1){
                dep[y]=dep[x]+1;
                if(vis[y]==0){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
int dfs(int x,int flw){
    if(x==t){
        flg=1,ans+=flw;
        return flw;
    }
    int rest=flw;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(worth[i]&&dep[y]==dep[x]+1){
            int newflw=dfs(y,min(rest,worth[i]));
            if(newflw>0){
                rest-=newflw;
                worth[i]-=newflw,worth[rev[i]]+=newflw;
                if(rest==0)
                    break;
            }
            else dep[y]=0;
        }
    }
    return flw-rest;
}
int Dinic(){
    ans=0;
    while(1){
        bfs();
        if(dep[t]==inf)
            break;
        flg=1;
        while(flg){
            flg=0;
            dfs(s,inf);
        }
    }
    return ans;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s1,&t1);
    s2=n+1,t2=n+2;
    s=s2,t=t2;
    for(i=1;i<=m;i++){
        int x,y,p,q;
        scanf("%d%d%d%d",&x,&y,&p,&q);
        in[y]+=p,out[x]+=p;
        addedge(x,y,q-p);
    }
    for(i=1;i<=n;i++){
        if(in[i]>out[i])
            addedge(s,i,in[i]-out[i]),sum+=in[i]-out[i];
        else addedge(i,t,out[i]-in[i]);
    }
    addedge(t1,s1,inf);
    if(Dinic()!=sum){
        puts("please go home to sleep");
        return 0;
    }
    anss=worth[e];
    worth[e]=worth[rev[e]]=0;
    s=s1,t=t1;
    anss+=Dinic();
    printf("%d\n",anss);
    return 0;
}

有源汇上下界最小流

我们看到有源点和汇点的上下界最小流，即在可行流的基础上要求流量最小。

我们先跑一遍可行流，设可行流为$flow1$，则最小流为可行流$-$还能向下浮动的流量$flow2$。

其实我们可以发现还能向下浮动的流量就是从原图汇点到原图源点的最大流（感性理解）。

因此步骤为：
1. 跑出一个有源汇上下界可行流，如果满流则设其答案为$flow1$，否则不存在答案。
2. 删去从原图汇点到原图源点的边。
3. 跑从原图汇点到原图源点的最大流，设答案为$flow2$，则总答案$ans=flow1-flow2$。

代码：

#include<stdio.h>
#include<queue>
#define inf 2147483647
using namespace std;
const int maxn=60005,maxm=1000005;
int i,j,k,m,n,s,t,s1,t1,s2,t2,e,flg,ans,sum,anss;
int start[maxn],to[maxm],then[maxm],worth[maxm],rev[maxm],dep[maxn],vis[maxn],in[maxn],out[maxn];
queue<int>q;
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y,int z,int r){
    then[++e]=start[x],start[x]=e,to[e]=y,worth[e]=z,rev[e]=r;
}
inline void addedge(int x,int y,int z){
    add(x,y,z,e+2),add(y,x,0,e);
}
void bfs(){
    while(!q.empty())
        q.pop();
    for(int i=1;i<maxn;i++)
        dep[i]=inf,vis[i]=0;
    dep[s]=0;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=start[x];i;i=then[i]){
            int y=to[i];
            if(worth[i]&&dep[y]>dep[x]+1){
                dep[y]=dep[x]+1;
                if(vis[y]==0){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
int dfs(int x,int flw){
    if(x==t){
        flg=1,ans+=flw;
        return flw;
    }
    int rest=flw;
    for(int i=start[x];i;i=then[i]){
        int y=to[i];
        if(worth[i]&&dep[y]==dep[x]+1){
            int newflw=dfs(y,min(rest,worth[i]));
            if(newflw>0){
                rest-=newflw;
                worth[i]-=newflw,worth[rev[i]]+=newflw;
                if(rest==0)
                    break;
            }
            else dep[y]=0;
        }
    }
    return flw-rest;
}
int Dinic(){
    ans=0;
    while(1){
        bfs();
        if(dep[t]==inf)
            break;
        flg=1;
        while(flg){
            flg=0;
            dfs(s,inf);
        }
    }
    return ans;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s1,&t1);
    s2=n+1,t2=n+2;
    s=s2,t=t2;
    for(i=1;i<=m;i++){
        int x,y,p,q;
        scanf("%d%d%d%d",&x,&y,&p,&q);
        in[y]+=p,out[x]+=p;
        addedge(x,y,q-p);
    }
    for(i=1;i<=n;i++){
        if(in[i]>out[i])
            addedge(s,i,in[i]-out[i]),sum+=in[i]-out[i];
        else addedge(i,t,out[i]-in[i]);
    }
    addedge(t1,s1,inf);
    if(Dinic()!=sum){
        puts("please go home to sleep");
        return 0;
    }
    anss=worth[e];
    worth[e]=worth[rev[e]]=0;
    s=t1,t=s1;
    anss-=Dinic();
    printf("%d\n",anss);
    return 0;
}

有源汇上下界最小费用可行流

我们开始考虑有源点和汇点的最小费用可行流，即给定一张图，每条边有出点，入点，费用，下界与上界，求安排每条边的流量使其满足上界与下界，且需要的费用最小（总费用等于每条边的费用单价乘上这条边实际的流量）。

我们先建一边有源汇上下界最大流的图，并加上费用，但是这里有一个小问题，因为少算了一个下界，因此我们要把下界的费用补回来，记$ans1$为所有边的容量下界乘上其费用的和。

然后我们发现为了让有源汇上下界最大流的图中虚拟源点和虚拟汇点连的边满流，我们肯定要选择最小费用最大流，这样不仅满足最小费用，还可以尽量跑满这些与虚拟源汇相连的边。

如果这些边没有满流，肯定不存在可行流，否则这次最小费用最大流的费用$ans2$就为答案的另一部分。

因此步骤为：
1. 按照有源汇上下界最大流建图（注意要加上费用，其余没什么区别）。
2. 记录所有边的容量下界乘上其费用的和为$ans1$。
3. 跑一遍从实际源点到实际汇点的最大流，记为$ans2$。
4. 答案$ans=ans1+ans2$

代码：

#include<stdio.h>
#include<queue>
#define inf 1000000000
using namespace std;
const int maxn=5005,maxm=100005;
int i,j,k,m,n,s1,t1,s2,t2,s,t,e,flw,ans1,ans2;
int start[maxn],to[maxm],then[maxm],limit[maxm],worth[maxm],rev[maxm],dis[maxn],vis[maxn],rec[maxn],in[maxn],out[maxn];
queue<int>q;
inline int min(int a,int b){
    return a<b? a:b;
}
inline void add(int x,int y,int z,int w,int r){
    then[++e]=start[x],start[x]=e,to[e]=y,limit[e]=z,worth[e]=w,rev[e]=r;
}
inline void addedge(int x,int y,int z,int w){
    add(x,y,z,w,e+2),add(y,x,0,-w,e);
}
int check(){
    for(int i=1;i<maxn;i++)
        dis[i]=inf,vis[i]=0;
    while(!q.empty())
        q.pop();
    dis[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=start[x];i;i=then[i]){
            int y=to[i];
            if(dis[y]>dis[x]+worth[i]&&limit[i]){
                dis[y]=dis[x]+worth[i],rec[y]=i;
                if(vis[y]==0)
                    vis[y]=1,q.push(y);
            }
        }
    }
    return dis[t]==inf? 0:1;
}
void work(){
    int minn=inf;
    for(int now=t;now!=s;now=to[rev[rec[now]]])
        minn=min(minn,limit[rec[now]]);
    flw+=minn;
    for(int now=t;now!=s;now=to[rev[rec[now]]])
        limit[rec[now]]-=minn,limit[rev[rec[now]]]+=minn,ans2+=worth[rec[now]]*minn;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s1,&t1);
    s2=n+1,t2=n+2;
    for(i=1;i<=m;i++){
        int x,y,w,l,r;
        scanf("%d%d%d%d%d",&x,&y,&w,&l,&r);
        addedge(x,y,r-l,w);
        ans1+=l*w,in[y]+=l,out[x]+=l;
    }
    addedge(t1,s1,inf,0);
    for(i=1;i<=n;i++){
        if(in[i]>out[i])
            addedge(s2,i,in[i]-out[i],0);
        else addedge(i,t2,out[i]-in[i],0);
    }
    s=s2,t=t2;
    while(check())
        work();
    printf("%d\n",ans1+ans2);
    return 0;
}

题单

LOJ

• #115. 无源汇有上下界可行流：RT
• #116. 有源汇有上下界最大流：RT
• #117. 有源汇有上下界最小流：RT

洛谷

• P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流：板子题，有源汇上下界最大流（其实题意有点迷）
• P4843 清理雪道：有源汇上下界最小流，可以用费用流实现
• P4043 [AHOI2014/JSOI2014]支线剧情：有源汇上下界最小费用可行流
• P2304 [NOI2015]小园丁与老司机：毒瘤题，dp+无源汇上下界最小流？
• P4553 80人环游世界：有源汇上下界最小费用可行流
• CF708D Incorrect Flow：有源汇上下界最小费用可行流
• P4311 士兵占领：有源汇上下界最小流（数据珂能有误（似乎没有判无解））
• P4194 矩阵：二分答案+有源汇上下界可行流
• CF704D Captain America：有源汇上下界最大流
• P3980 [NOI2008]志愿者招募：无源汇上下界最小费用可行流，可以用费用流实现 正解费用流
• UVA1104 芯片难题 Chips Challenge：虽然我不会做，但是感谢巨飞的Dr冯的贡献

POJ

• Budget：有源汇上下界可行流
• Crazy Circuits：有源汇上下界最小流

BZOJ

• XWW的难题：有源汇上下界最大流