P14580 【模板】有源汇上下界最小流题解

_Dolphin_ · 2025-12-24 20:19:25 · 题解

这是一篇图解。

前置知识

网络最大流

上下界网络流定义

设有一个网络 G=(V,E)（即点集为 V，边集为 E 的网络），每条网络中的边 (u,v)，都有其流量为 f(u,v)，容量为 c(u,v)。

首先，我们知道对于一个普通网络流问题，需要满足以下限制：

容量限制，即对于任意一条边 (u,v)\in E，满足 0\leq f(u,v)\leq c(u,v)。
流量守恒，即除源汇点外任意一点 u，满足 \sum_{(v,u)\in E}f(v,u)=\sum_{(u,v)\in E}f(u,v)。

那么上下界网络流，顾名思义，就是每条边除了有流量上界（容量），还有一个流量下界，记作 b(u,v)。那么对于每条边 (u,v)\in E，需要满足 b(u,v)\leq f(u,v)\leq c(u,v)。

那么怎么解决这种问题呢？我们先从最基础的情况开始。

无源汇上下界可行流

题目传送门

无源汇，就是说网络是没有源汇点的，那么每个点就都要满足流量守恒。我们要在一个这样的网络上求出一个可行（满足流量限制）的流。

给定一个无源汇上下界网络：

每条边上的数分别是流量上界和下界，大家可以先尝试瞪出来一个可行流。

先满足下界，我们将每条边的下界拆分出来，组成下界网络，下界网络中的边直接满流。

上界减下界剩下容量的组成差值网络，这样这个网络就没有下界限制了。

但是显然在差值网络上直接跑流是不对的，这可能会使总流量（下界加上差值网络中的流量）不守恒。

因为下界网络不是合法的网络，它不满足流量守恒，我们自然也不能简单地让差值网络满足流量守恒。

那么将下界网络每个点流出的量和流入的量统计起来。

有些点在下界网络中流入比流出多一些（紫色的点），也有一些流出比流入多（橙色的点）。

将流入流量与流出流量作差就能体现出来，我们将这个差叫做这个点的下界净流量。

这样紫点的下界净流量大于 0，而橙点的下界净流量小于 0。

为了让总流量平衡，我们需要在差值网络中把下界净流量抵消掉。

对于每个紫点，它在下界网络中流入更多，我们就让其在差值网络中少流入一些，少流入的量也就是它的下界净流量。

怎么实现这样的效果呢？网络流的性质是流量守恒，为了让这些点少流入一些，我们可以从原网络外为其补齐流入流量。那么新建源点 s，从 s 到当前点 u 连边，容量为 u 的下界净流量。

这样 u 的流入流量（不计 (s,u) 的流量）就会少一些，从而它的下界净流量就被抵消掉了。

与紫点相反，对于每个橙点，它在下界网络中流出更多，我们就让其在差值网络中少流出一些，少流出的量也就是它的下界净流量的绝对值。

为了让这些点少流出一些，我们可以让它的一部分流入的流量流出原网络。那么新建源点 t，从 u 到当前点 t 连边，容量为 u 的下界净流量的绝对值。

接下来从 s 到 t 跑最大流，如果所有附加边都满流，就代表所有点的流量守恒都被满足，也就是说原网络有可行流。

但是如果有附加边没有满流，那么原图就没有可行流。

把源汇点删掉，差值网络中边的流量就是可行流除去下界的部分。

将差值网络跑出来的流量加到下界上，就是一组可行流了。

最后得出的可行流是这样的，有人瞪出来的和这个一样吗？

:::success[Code]

#include<bits/stdc++.h>
#define afor(i,x,y) for(int i=(x);i<=(y);i++)
#define bfor(i,x,y) for(int i=(x);i>=(y);i--)
using namespace std;
typedef long long ll;
const int N=1e6+10,M=1e6+10;
struct net{
    int tot,maxflow,head[N],cur[N],dep[N],to[M],nxt[M];
    int cap[M],flow[M];
    bool vis[N];
    void clear() {tot=-1,memset(head,-1,sizeof head);}
    void _add(int x,int y,int z) {
        to[++tot]=y,cap[tot]=z,flow[tot]=0;
        nxt[tot]=head[x],head[x]=tot;
    }
    void add(int x,int y,int z) {_add(x,y,z),_add(y,x,0);}
} g;
bool bfs(int s,int t) {
    memset(g.dep,0,sizeof g.dep);
    queue<int> q;
    q.push(s),g.dep[s]=1;
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=g.head[x];~i;i=g.nxt[i]) {
            int y=g.to[i];
            if(!g.dep[y]&&g.flow[i]<g.cap[i])
                q.push(y),g.dep[y]=g.dep[x]+1;
        }
    }
    return g.dep[t];
}
int dfs(int x,int t,int now) {
    if(x==t) return now;
    int res=0;
    g.vis[x]=1;
    for(int i=g.cur[x];~i&&res<now;i=g.nxt[i]) {
        g.cur[x]=i;
        int y=g.to[i];
        if(!g.vis[y]&&g.dep[y]==g.dep[x]+1&&g.flow[i]<g.cap[i]) {
            int d=dfs(y,t,min(now-res,g.cap[i]-g.flow[i]));
            res+=d,g.flow[i]+=d,g.flow[i^1]-=d;
        }
    }
    g.vis[x]=0;
    return res;
}
int dinic(int s,int t) {
    g.maxflow=0;
    while(bfs(s,t)) {
        memcpy(g.cur,g.head,sizeof g.cur);
        g.maxflow+=dfs(s,t,1e9);
    }
    return g.maxflow;
}
int n,m,s,t,sum,d[N],id[M],l[M];
int main() {
    g.clear();
    scanf("%d%d",&n,&m);
    s=n+1,t=n+2;
    afor(i,1,m) {
        int x,y,r;
        scanf("%d%d%d%d",&x,&y,&l[i],&r);
        g.add(x,y,r-l[i]);
        d[x]+=l[i],d[y]-=l[i];
        id[i]=g.tot^1;
    }
    afor(i,1,n) {
        if(d[i]>0) g.add(i,t,d[i]),sum+=d[i];
        if(d[i]<0) g.add(s,i,-d[i]);
    }
    if(dinic(s,t)!=sum) return printf("No"),0;
    printf("Yes\n");
    afor(i,1,m) printf("%d\n",l[i]+g.flow[id[i]]);
    return 0;
}

:::

有源汇上下界可行流

处理完无源汇上下界可行流，后面的事情就简单了。

给定有源汇上下界网络，源点为 s，汇点为 t：

现在要求出其上的一个可行流，满足除源汇点外所有点流量守恒。

我们可以将其转化为无源汇上下界可行流问题，只要新建一条从 t 到 s，限制为 [0,+\infty] 的边。

这样所有从 s 到 t 的流量都会从这条边流回 s。

接下来跑无源汇上下界可行流，注意原图源汇点 s 和 t 与附加源汇点 s' 和 t' 不同。

注意此处省略了下界网络。

跑可行流，此时附加边 (t,s) 上的流量即为可行流流量。

有源汇上下界最大流

题目传送门

首先给定有源汇上下界网络（与上面的相同）：

先跑出一个可行流。

删去所有附加边。

然后用原来的源汇在残量网络求解一次最大流（此处为 2），加上可行流（此处为 3）即为答案。

其实不需要删去所有附加边，只需将 (t,s) 删去即可，因为那两个附加节点是不影响最大流求解的。

:::success[Code]

#include<bits/stdc++.h>
#define afor(i,x,y) for(int i=(x);i<=(y);i++)
#define bfor(i,x,y) for(int i=(x);i>=(y);i--)
using namespace std;
typedef long long ll;
const int N=1e6+10,M=1e6+10;
struct net{
    int tot,maxflow,head[N],cur[N],dep[N],to[M],nxt[M];
    int cap[M],flow[M];
    bool vis[N];
    void clear() {tot=-1,memset(head,-1,sizeof head);}
    void _add(int x,int y,int z) {
        to[++tot]=y,cap[tot]=z,flow[tot]=0;
        nxt[tot]=head[x],head[x]=tot;
    }
    void add(int x,int y,int z) {_add(x,y,z),_add(y,x,0);}
} g;
bool bfs(int s,int t) {
    memset(g.dep,0,sizeof g.dep);
    queue<int> q;
    q.push(s),g.dep[s]=1;
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=g.head[x];~i;i=g.nxt[i]) {
            int y=g.to[i];
            if(!g.dep[y]&&g.flow[i]<g.cap[i])
                q.push(y),g.dep[y]=g.dep[x]+1;
        }
    }
    return g.dep[t];
}
int dfs(int x,int t,int now) {
    if(x==t) return now;
    int res=0;
    g.vis[x]=1;
    for(int i=g.cur[x];~i&&res<now;i=g.nxt[i]) {
        g.cur[x]=i;
        int y=g.to[i];
        if(!g.vis[y]&&g.dep[y]==g.dep[x]+1&&g.flow[i]<g.cap[i]) {
            int d=dfs(y,t,min(now-res,g.cap[i]-g.flow[i]));
            res+=d,g.flow[i]+=d,g.flow[i^1]-=d;
        }
    }
    g.vis[x]=0;
    return res;
}
int dinic(int s,int t) {
    g.maxflow=0;
    while(bfs(s,t)) {
        memcpy(g.cur,g.head,sizeof g.cur);
        g.maxflow+=dfs(s,t,1e9);
    }
    return g.maxflow;
}
int n,m,s,t,id,sum,d[N];
int main() {
    g.clear();
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int S=n+1,T=n+2;
    afor(i,1,m) {
        int x,y,l,r;
        scanf("%d%d%d%d",&x,&y,&l,&r);
        g.add(x,y,r-l);
        d[x]+=l,d[y]-=l;
    }
    g.add(t,s,1e9),id=g.tot^1;
    afor(i,1,n) {
        if(d[i]>0) g.add(i,T,d[i]),sum+=d[i];
        if(d[i]<0) g.add(S,i,-d[i]);
    }
    if(dinic(S,T)!=sum) return printf("N"),0;
    int ans=g.flow[id];
    g.flow[id]=g.flow[id^1]=g.cap[id]=0;
    ans+=dinic(s,t);
    printf("%d",ans);
    return 0;
}

:::

有源汇上下界最小流

题目传送门

与有源汇上下界最大流类似，答案为可行流减去残量网络从 t 到 s 的最大流，可以理解为要退掉尽可能多的流。

:::success[Code]

#include<bits/stdc++.h>
#define afor(i,x,y) for(int i=(x);i<=(y);i++)
#define bfor(i,x,y) for(int i=(x);i>=(y);i--)
using namespace std;
typedef long long ll;
const int N=1e6+10,M=1e6+10;
struct net{
    int tot,maxflow,head[N],cur[N],dep[N],to[M],nxt[M];
    int cap[M],flow[M];
    bool vis[N];
    void clear() {tot=-1,memset(head,-1,sizeof head);}
    void _add(int x,int y,int z) {
        to[++tot]=y,cap[tot]=z,flow[tot]=0;
        nxt[tot]=head[x],head[x]=tot;
    }
    void add(int x,int y,int z) {_add(x,y,z),_add(y,x,0);}
} g;
bool bfs(int s,int t) {
    memset(g.dep,0,sizeof g.dep);
    queue<int> q;
    q.push(s),g.dep[s]=1;
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=g.head[x];~i;i=g.nxt[i]) {
            int y=g.to[i];
            if(!g.dep[y]&&g.flow[i]<g.cap[i])
                q.push(y),g.dep[y]=g.dep[x]+1;
        }
    }
    return g.dep[t];
}
int dfs(int x,int t,int now) {
    if(x==t) return now;
    int res=0;
    g.vis[x]=1;
    for(int i=g.cur[x];~i&&res<now;i=g.nxt[i]) {
        g.cur[x]=i;
        int y=g.to[i];
        if(!g.vis[y]&&g.dep[y]==g.dep[x]+1&&g.flow[i]<g.cap[i]) {
            int d=dfs(y,t,min(now-res,g.cap[i]-g.flow[i]));
            res+=d,g.flow[i]+=d,g.flow[i^1]-=d;
        }
    }
    g.vis[x]=0;
    return res;
}
int dinic(int s,int t) {
    g.maxflow=0;
    while(bfs(s,t)) {
        memcpy(g.cur,g.head,sizeof g.cur);
        g.maxflow+=dfs(s,t,1e9);
    }
    return g.maxflow;
}
int n,m,s,t,id,sum,d[N];
int main() {
    g.clear();
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int S=n+1,T=n+2;
    afor(i,1,m) {
        int x,y,l,r;
        scanf("%d%d%d%d",&x,&y,&l,&r);
        g.add(x,y,r-l);
        d[x]+=l,d[y]-=l;
    }
    g.add(t,s,1e9),id=g.tot^1;
    afor(i,1,n) {
        if(d[i]>0) g.add(i,T,d[i]),sum+=d[i];
        if(d[i]<0) g.add(S,i,-d[i]);
    }
    if(dinic(S,T)!=sum) return printf("N"),0;
    int ans=g.flow[id];
    g.flow[id]=g.flow[id^1]=g.cap[id]=0;
    ans-=dinic(t,s);
    printf("%d",ans);
    return 0;
}

:::

练习

P5192 Shoot the Bullet | 东方文花帖
P4843 清理雪道
P4043 AHOI2014/JSOI2014 支线剧情
P4194 矩阵
CF708D Incorrect Flow
CF704D Captain America
CF1416F Showing Off
UVA1104 Chips Challenge
P2304 NOI2015 小园丁与老司机

希望有帮到大家，有问题欢迎在讨论区提出。

题解和图片制作不易，点个赞再走吧，求求了！

P14580 【模板】有源汇上下界最小流 题解

前置知识

上下界网络流定义

无源汇上下界可行流

有源汇上下界可行流

有源汇上下界最大流

有源汇上下界最小流

练习

P14580 【模板】有源汇上下界最小流题解