网络流

liushuangning · 2025-01-19 11:14:43 · 算法·理论

本蒟蒻第一次学网络流，如果有错误，欢迎各位大佬指出！

基础与定义

流网络

记作 G_f。

残留网络是和可行流一一对应的，可行流不同，残留网络也不同。

像这两个流网络，下面的就是上面的残留网络。

增广路径

定义：在残留网络里面，从源点出发，沿着容量大于 0 的边，如果能够走到汇点的话，那么这条路径就被称为增广路径。

若流网络 G 的一条可行流 f 的残留网络 G_f 中不存在增广路径的话，那么 f 就是 G 的最大流。

割

定义

将点集 V 分成两个集合 S,T，使得 S\cup T=V,S\cap T=\varnothing，且 s\in S,t\in T。

容量

所有从 S 指向 T 的边的容量之和。

注意：只算从 S 指向 T 的边。

最小割：割的容量最小的那一种分割方案。

分割方案数：2^{n-2} 种。

流量

性质：\forall[S,T]\forall f

• 割的流量 f(S,T)= 可行流的流量 |f|。

所以最大流 \le 最小割。

最大流最小割定理

对于某一个流网络 G(V,E)，以下三个条件是等价的：

• 可行流 f 是最大流；

• 可行流 f 的残留网络中不存在增广路径；

• 存在某个割 [S,T]，使得 |f|=c(S,T)。

最大流

算法模板

EK 算法

while(   ){
    1.找增广路径（BFS）
    2.更新残留网络
}

对于更新残留网络：

时间复杂度：O(nm^2)。

但是

yxc:网络流算法的时间复杂度跟放屁一样，它的实际效率是非常高的。

存图：第 0 条边是正向边，第 1 条边是第 0 条边的反向边，以此类推。

如果要找 i 这条边的反向边就是 i\oplus 1。

参考代码（根据此题写的代码，如果你没有买课，这里是题面）：

唐氏马蜂，请勿吐槽。

#include<bits/stdc++.h>
#define mems(a,b) memset(a,b,sizeof a)
using namespace std;
const int N=1010,M=20010,inf=0x3f3f3f3f;//这里的inf只要比10000大就行
int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;//f为容量
int q[N],d[N],pre[N];//d为从起点走到当前点的所有边上的容量最小值，pre为前驱边
bool st[N];
void add(int a,int b,int c){
    //建正向边
    e[idx]=b;
    f[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
    //建反向边
    e[idx]=a;
    f[idx]=0;
    ne[idx]=h[b];
    h[b]=idx++;
}
bool bfs(){
    int hh=0,tt=0;
    mems(st,0);
    q[0]=S;
    st[S]=true;
    d[S]=inf;
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i/*等价于i!=-1*/;i=ne[i]){
            int ver=e[i];
            if(!st[ver] && f[i]>0){
                st[ver]=true;
                d[ver]=min(d[t],f[i]);
                pre[ver]=i;
                if(ver==T) return true;//找到了增广路径
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int EK(){
    int r=0;
    while(bfs()){
        r+=d[T];
        for(int i=T;i!=S;i=e[pre[i]^1]/*这条边的编号为pre[i]，反向边就是pre[i]^1，反向边指向的点的编号就是e[pre[i]^1]*/){
            f[pre[i]]-=d[T];
            f[pre[i]^1]+=d[T];
        }
    }
    return r;
}
int main(){
    cin>>n>>m>>S>>T;
    mems(h,-1);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<EK();
    return 0;
}

注：如果你想在洛谷上 AC 此题，请开 long long，并扩大 inf。

dinic 算法

原题，转存。

EK 算法每次只会搜索流网络中的一条增广路径，但是一个流网络中可能有很多增广路径，dinic 算法的优化思路就是每次将所有增广路径全部搜索一遍。

但是如果有环的话，dinic 算法就会死循环，所以我们引入了分层图的概念。

也就是说，我们把一张图做成一层一层的，并严格要求每次在寻找增广路径的时候，从起点开始，只能从前一层走到后一层，直到走到终点，这样就会保证一定没有环路。

这个点的层数我们定义为到起点的最短距离。

所以 dinic 算法的思路就是：

1. BFS，建立分层图；

2. DFS，在分层图中搜索全部增广路径。

当前弧优化：

假设现在已经建立完分层图，那么我们维护从起点到这个点可流过流量的最大值，也就是容量的最小值，当这个点继续往后搜的时候，再看一下从这个点到终点的所有路径中，最多可以流过多少流量，再比较它的一条临边到终点能流过的流量，如果这条边能流过的流量已经满了的话，那么以后枚举到这个点的时候就不需要再枚举这条临边了。

我们用水管来理解，比如这个节点相邻的一条水管已经满了的话，那么考虑方案的时候就不用再考虑这条水管了。

注：dinic 对优化是极其敏感的，如果一个优化写错了，或者少写一个优化都有可能 TLE。

参考代码：

//与EK算法相同的地方不再写注释
#include<bits/stdc++.h>
#define mems(a,b) memset(a,b,sizeof a)
using namespace std;
const int N=10010,M=200010,inf=0x3f3f3f3f;
int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;
int q[N],d[N],cur[N];//d为分层图层数，cur为当前弧优化，表示当前这个点的第一个没有满的临边
void add(int a,int b,int c){
    e[idx]=b;
    f[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
    e[idx]=a;
    f[idx]=0;
    ne[idx]=h[b];
    h[b]=idx++;
}
bool bfs(){
    int hh=0,tt=0;
    mems(d,-1);
    q[0]=S;
    d[S]=0;
    cur[S]=h[S];//当前弧初始化成第一条边
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int ver=e[i];
            if(d[ver]==-1 && f[i]>0){
                d[ver]=d[t]+1;//更新最短距离，be like SPFA
                cur[ver]=h[ver];//更新这个点的当前弧
                if(ver==T) return true;//找到了增广路径
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int find(int u/*从u这个点开始搜*/,int limit/*从起点能够流向u这个点的最大流量*/){
    if(u==T) return limit;
    int flow=0;//表示从u这个点向后流过最大的流量
    for(int i=cur[u];~i && flow<limit/*后面流的最大流量要保证小于前面流过的最大流量，如果等于的话，也就没有必要再搜索了*/;i=ne[i]){
        cur[u]=i;//将当前弧设为i，因为i之前的边已经满了，否则不会搜到i这条边
        int ver=e[i];
        if(d[ver]==d[u]+1/*按分层图的顺序*/ && f[i]>0){
            int t=find(ver,min(f[i],limit-flow));
            if(t==0) d[ver]=-1;//如果当前这个点不可用（可流过的流量为0），就把这个点删掉
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())//bfs函数即可以建立分层图，还可以返回有没有增广路径
        while(flow=find(S,inf)) r+=flow;//如果有增广路径，就在当前的分层图中累加全部增广路径的流量，如果不套while的话，有时会因为inf太小榨不干
    return r;
}
int main(){
    cin>>n>>m>>S>>T;
    mems(h,-1);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<dinic();
    return 0;
}

放屁时间复杂度：O(n^2m)。

应用概括

问：给我们一个问题 P，该如何把它转化为一个流网络 G 呢？

我们要证明下面两个条件：

• 问题 P 中任意一个可行解都可以在流网络 G 中对应一条可行流。

• 流网络 G 中的任意一条可行流都可以在问题 P 中对应一个可行解。

证明完这两个条件后，问题 P 中可行解的最大值就可以转化成流网络 G 中的最大流。

如果要求最小解，就可以对应到最小割。

二分图

原题，洛谷原题。

相比较我们之前学过的二分图最大匹配算法，最大流算法会更快。

比如说比较匈牙利算法和 dinic 算法。

匈牙利算法时间复杂度：O(nm)。

dinic 算法时间复杂度：O(m\sqrt{n})。

那么问题来了：用网络流解决二分图最大匹配，要怎么建图呢？

比如给了我们两个点集 V_1 和 V_2，就可以这样建图：

1. 建立一个虚拟源点 S，并向点集 V_1 的每一个点连一条容量为 1 的边。

2. 建立一个虚拟汇点 T，并将点集 V_2 的每一个点向 T 连一条容量为 1 的边。

3. 对于两个点集之间的边，就连一条容量为 1 的边。

注意：这里的前提是流量为整数，否则可行流不能对应到可行解。

但是我们要求的整数值最大流的集合，是在整个最大流集合内的，也就是说，我们要求的答案是算法给出来的答案的子集。

对于这种情况，我们自习观察一下我们的 dinic 算法，发现我们用过的变量都是整数值变量，所以我们求的可行流，也就都是整数值可行流（这很显然，各位大佬应该不用想就知道）。

参考代码：

#include<bits/stdc++.h>
#define mems(a,b) memset(a,b,sizeof a)
using namespace std;
const int N=110,M=5210,inf=0x3f3f3f3f;
int n,m,S,T;
int h[N],e[M],ne[M],f[M],idx;
int q[N],d[N],cur[N];
void add(int a,int b,int c){
    e[idx]=b;
    f[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
    e[idx]=a;
    f[idx]=0;
    ne[idx]=h[b];
    h[b]=idx++;
}
bool bfs(){
    int hh=0,tt=0;
    mems(d,-1);
    q[0]=S;
    d[S]=0;
    cur[S]=h[S];
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int ver=e[i];
            if(d[ver]==-1 && f[i]>0){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i && flow<limit;i=ne[i]){
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1 && f[i]>0){
            int t=find(ver,min(f[i],limit-flow));
            if(t==0) d[ver]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())
        while(flow=find(S,inf)) r+=flow;
    return r;
}
int main(){
    cin>>m>>n;
    S=0,T=n+1;
    mems(h,-1);
    for(int i=1;i<=m;i++) add(S,i,1);
    for(int i=m+1;i<=n;i++) add(i,T,1);
    int a,b;
    while(scanf("%d%d",&a,&b) && a!=-1) add(a,b,1);
    cout<<dinic()<<endl;
    for(int i=0;i<idx;i+=2)//枚举所有正向边
        if(e[i]>m && e[i]<=n && f[i]==0) printf("%d %d\n",e[i^1],e[i]);//这条边在两个点集中间，且正向边的流量为0（被选了）
    return 0;
}

原题，洛谷原题。

对于这道题，我们知道 m 个单位，n 个圆桌，每个单位的人数分别是 r_1,r_2,...,r_m，每个圆桌的容量分别是 c_1,c_2,...,c_n。

要求：每张圆桌上，不能有两个人在同一个单位。

这题还是一道二分图的问题，m 个单位可以画 m 个点，n 张圆桌可以画 n 个点，左边每个点向右边每个点连一条容量为 1 的边。

但是这题的特殊之处就在于：每个点可以选多次。比如说第一个单位有两个人，那么这个点是可以在两条边里的。也就是说，有些边是可以共用某些点的。这道题就是二分图的多重匹配问题。

我们可以参考上一题的建图方式，建立源点和汇点，源点向左边每个点连一条容量为 r_i 的边（因为这个点可以用 r_i 次），右边每个点向汇点连一条容量为 c_i 的边。

下面是一种情况：

题目要求我们输出一种方案，使得所有代表都有地方坐，也就是从源点出发的边都是满流。

那么问题有没有解，就相当于流网络存不存在一条可行流，使得从源点出发的边都是满流。其实就是看一下流网络的最大流，从源点出发的边是不是都是满流。

也就是计算最大流是不是等于总人数。

输出方案的时候，只要看一下从左边出发的每条边，哪些边是满流的，就说明左边这个单位向右边那张桌子派了一名代表。

参考代码：

#include<bits/stdc++.h>
#define mems(a,b) memset(a,b,sizeof a)
using namespace std;
const int N=430,M=(150*270+N)*2,inf=0x3f3f3f3f;
int m,n,S,T;
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N],cur[N];
void add(int a,int b,int c){
    e[idx]=b;
    f[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
    e[idx]=a;
    f[idx]=0;
    ne[idx]=h[b];
    h[b]=idx++;
}
bool bfs(){
    int hh=0,tt=0;
    mems(d,-1);
    q[0]=S;
    d[S]=0;
    cur[S]=h[S];
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int ver=e[i];
            if(d[ver]==-1 && f[i]>0){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i && flow<limit;i=ne[i]){
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1 && f[i]>0){
            int t=find(ver,min(f[i],limit-flow));
            if(t==0) d[ver]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())
        while(flow=find(S,inf)) r+=flow;
    return r;
}
int main(){
    cin>>m>>n;
    S=0;
    T=m+n+1;
    mems(h,-1);
    int tot=0;//总人数
    for(int i=1;i<=m;i++){
        int c;
        scanf("%d",&c);
        add(S,i,c);
        tot+=c;
    }
    for(int i=1;i<=n;i++){
        int c;
        scanf("%d",&c);
        add(i+m,T,c);
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++) add(i,j+m,1);
    if(dinic()!=tot) puts("0");//无解
    else{
        puts("1");
        for(int i=1;i<=m;i++){
            for(int j=h[i];~j;j=ne[j])
                if(e[j]>m && e[j]<=m+n && !f[j]) printf("%d ",e[j]-m);
            puts("");
        }
    }
    return 0;
}

上下界可行流

无源汇上下界可行流

原题，转存。

原先的流量要满足的条件是：0\le f(u,v)\le c(u,v)。

现在的流量要满足的条件是：c(u,v)\le f(u,v)\le d(u,v)。

为了方便，下面把 c(u,v) 叫做 c_l(u,v)，d(u,v) 叫做 c_u(u,v)。

设原网络是 G，原网络的一条可行流是 f，我们希望把 (G,f) 变成 (G',f')，使得 G' 符合我们平时见到的流网络。

原网络的条件为：c_l(u,v)\le f(u,v)\le c_u(u,v)。

将每一项都减去 c_l(u,v)，得：0\le f(u,v)-c_l(u,v)\le c_u(u,v)-c_l(u,v)，这样就是我们平常见到的流网络的流量限制了。

然后我们再将求出来的方案加上 c_l(u,v)，这样得到的流网络满足容量限制，但是不一定满足流量守恒，比如说这样的一个局部：

每条边的容量都加上 c_l(u,v) 的话，就会将进入的流量多减 C_{\text{out}}=\sum_{v\in V} c_l(x,v)，多加 C_{\text{in}}=\sum_{v\in V} c_l(v,x)，很有可能这个点出去的流量和进入的流量不相等。

其实我们只要从源点或汇点连一条边补上流量就可以了，如果 C_{\text{out}}>C_{\text{in}}，只需要从源点连一条流量为 C_{\text{out}}-C_{\text{in}} 的边，那么现在的流量就守恒了。

#include<bits/stdc++.h>
#define mems(a,b) memset(a,b,sizeof a)
using namespace std;
const int N=210,M=(10200+N)*2,inf=0x3f3f3f3f;
int n,m,S,T;
int h[N],e[M],f[M],l[M],ne[M],idx;
int q[N],d[N],cur[N],A[N];//A[i]表示这个点进入的容量下界之和-出去的容量下界之和
void add(int a,int b,int c,int d){
    e[idx]=b;
    f[idx]=d-c;
    l[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
    e[idx]=a;
    f[idx]=0;
    ne[idx]=h[b];
    h[b]=idx++;
}
bool bfs(){
    int hh=0,tt=0;
    mems(d,-1);
    q[0]=S;
    d[S]=0;
    cur[S]=h[S];
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int ver=e[i];
            if(d[ver]==-1 && f[i]>0){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i && flow<limit;i=ne[i]){
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1 && f[i]>0){
            int t=find(ver,min(f[i],limit-flow));
            if(!t) d[ver]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())
        while(flow=find(S,inf)) r+=flow;
    return r;
}
int main(){
    cin>>n>>m;
    S=0;
    T=n+1;
    mems(h,-1);
    for(int i=0;i<m;i++){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
        A[a]-=c;
        A[b]+=c;
    }
    int tot=0;//从源点出发到每个点的容量下界之和
    for(int i=1;i<=n;i++){
        if(A[i]>0){
            add(S,i,0,A[i]);//从源点连边
            tot+=A[i];
        }
        else if(A[i]<0)
            add(i,T,0,-A[i]);//向汇点连边
    }
    if(dinic()!=tot) puts("NO");//不是满流，就说明无解
    else{
        puts("YES");
        for(int i=0;i<m*2;i+=2) printf("%d\n",f[i^1]+l[i]);
    }
    return 0;
}

有源汇上下界最大流

原题，转存。

这题规定了源点和汇点，从上一题的所有点都是流量守恒（不算自己增加的点），变成了除了源点和汇点，都是流量守恒。为了解决这个问题，我们可以从汇点向源点连一条容量为 +\infty 的边。

问：如何求最大流？

我们很容易想到下面的做法：先按上一题的做法转换流网络，并删掉那条刚加的边，再做一遍 dinic，就可以保证 s 到 t 没有增广路径，所以就求出了最大流。

但是这个证明是错误的，因为我们求出的残留网络是从 S 到 T 的残留网络，而我们要求的是从 s 到 t 的最大流，所以不能这样想。

我们选择原图 G 的一条可行流 f_0，通过之前的变换，成为图 G' 中特定的一条可行流 f_0'，然后求一下 f_0' 的残留网络 G'_{f_0'}，那么这个残留网络中 S 到 T 的满流就是 f_0'，那么这个可行流里面有一部分的流就是从 s 到 t 流过去的，流量就是之前加上的那条从 t 到 s 的流量，记为 f_{0\ s\rarr t}'，下面我们从 G'_{f_0'} 中找到所有 s 到 t 的可行流（右），再找到原图的所有可行流（左），我们只需要证明这两个集合中的可行流一一对应。

我们可以这样证明：左集合中任意一个元素可以在右集合中找到，右集合中的任意一个元素也可以再左集合中找到。

右到左：现在从右集合任取一个可行流，记为 f'_{s\rarr t}，那么不难发现 f'_{s\rarr t}+f_0' 仍然是一个 G' 的满流，也就是原图的一条可行流，所以说右边集合的任意一个元素可以找到左边集合的一个元素对应。

左到右：首先左集合的一条可行流 f 通过变换可以得到 G' 中的一个满流 f'，因为 G' 中的所有流都是满流，所以 f'-f_0' 中从 S 出发的所有边和流向 T 的所有边的流量都是 0，所以说所有的流量都在中间部分，也就是 s 到 t 的流量，那么左集合中的所有元素就可以对应到右集合的所有元素。

结论：如果要求左集合的最大值就相当于在右集合中求最大值。

如果要求最小流的话就是让 s 到 t 的流尽可能小，也就是让 t 到 s 的流尽可能大，就是求 t 到 s 的最大流。

参考代码：

#include<bits/stdc++.h>
#define mems(a,b) memset(a,b,sizeof a)
using namespace std;
const int N=210,M=(N+10000)*2,inf=0x3f3f3f3f;
int n,m,S,T;//S,T是虚拟的源汇
int h[N],e[M],f[M],ne[M],idx;
int q[N],d[N],cur[N],A[N];
void add(int a,int b,int c){
    e[idx]=b;
    f[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
    e[idx]=a;
    f[idx]=0;
    ne[idx]=h[b];
    h[b]=idx++;
}
bool bfs(){
    int hh=0,tt=0;
    mems(d,-1);
    q[0]=S;
    d[S]=0;
    cur[S]=h[S];
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int ver=e[i];
            if(d[ver]==-1 && f[i]>0){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T) return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}
int find(int u,int limit){
    if(u==T) return limit;
    int flow=0;
    for(int i=cur[u];~i && flow<limit;i=ne[i]){
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1 && f[i]>0){
            int t=find(ver,min(f[i],limit-flow));
            if(t==0) d[ver]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}
int dinic(){
    int r=0,flow;
    while(bfs())
        while(flow=find(S,inf)) r+=flow;
    return r;
}
int main(){
    int s,t;//题目给定的源汇
    cin>>n>>m>>s>>t;
    S=0,T=n+1;
    mems(h,-1);
    while(m--){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,d-c);
        A[a]-=c;
        A[b]+=c;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        if(A[i]>0){
            add(S,i,A[i]);
            tot+=A[i];
        }
        else if(A[i]<0) add(i,T,-A[i]);
    }
    add(t,s,inf);
    if(dinic()<tot) puts("No Solution");
    else{
        int ans=f[idx-1];//上面加的那条边的流量（因为满流，所以流量等于容量）
        S=s;
        T=t;
        f[idx-1]=f[idx-2]=0;//删边
        cout<<ans+dinic();
    }
    return 0;
}

有源汇上下界最小流

原题，转存。