网络流

基本概念

流网络

流网络中存在两个特殊点：源点和汇点；每条边存在一个容量，记作$c(u,v)$，若边不存在，则$c(u,v)=0$；用$f(u,v)$表示每条边的流量，即实际流过的流量值。

可行流

若一个可行流$f$满足：

容量限制：$0 \le f(u,v) \le c(u,v)$，即所有边的流量不超过边的容量
流量守恒：$v,x \in V/ {s,t},\sum_{(v,x)\in E}f(v,x)=\sum_{(x,v)\in E}f(x.v)$，即所有除了源点和汇点的点的流入总量等于流出总量

用$|f|$表示可行流$f$每秒从源点流出的流量，即$\sum_{(s,v)\in E}f(s,v)-\sum_{(v.s)\in E}f(v,s)$，

最大流

最大流就是最大可行流，即所有可行流中的最大值。

残留网络

对于每个可行流，都有对应的一个残留网络。

记可行流$f=(V,E)$的残留网络为$G_f$，则残留网络的$V_f=V,E_f=E$和$E$的所有反向边，反向边的边权$c’(u,v)=a \begin{cases}
c(u,v)-f(u,v) & (u,v)\in E \
f(u,v) & (v,u)\in E
\end{cases}$

定理：记原网络$G$的一个可行流为$f$，其残留网络$G_f$的一个可行流为$f’$，则$f+f’$也是$G$的一个可行流，且$|f+f’|=|f|+|f’|$。

增广路径

在残留网络中从源点出发沿着容量大于$0$的边如果能走到汇点，则这条路径为一条增广路径。

定理：若一个可行流$f$的残留网络中没有增广路径，则这个可行流一定是一个最大流。

割

在一个流网络$G=(V,E)$中选取两个点集$S,T$，满足$S\cap T=\phi,S\cup T=V$，且源点$s \in S$，汇点$t \in T$，则这种划分方案称为流网络的一个割。

割的容量：所有从$S$连向$T$的边的容量之和，即$c(S,T)=\sum_{u \in S} \sum_{v \in T} c(u,v)$。

最小割：所有割的割的容量最小的割。

割的流量：从$S$连向$T$的边的流量之和减去从$T$连向$S$的边的流量之和，即$f(S,T)=\sum_{u \in S} \sum_{v \in T} f(u,v)-\sum_{u \in T} \sum_{v \in S} f(u,v)$

性质：

对于任意一个割，割的流量小于等于割的容量，即$f(S,T)\le c(S,T)$
$f(X,Y)=-f(Y,X)$
$f(X,X)=0$
若$X\cap Y=\phi$，则$f(Z,X\cup Y)=f(Z,X)+f(Z,Y),f(X\cup Y,Z)=f(X,Z)+f(Y,Z)$
对于任意可行流$f$，任意割$[S,T]$，$|f| = f(S,T) \le c(S,T)$

最大流最小割定理：

在$G=(V,E)$中，$f$是最大流$\iff$ $G_f$中不存在增广路径 $\iff$ $\exist [S,T] ,|f|=c(S,T)$。

最大流

题目：洛谷P3376 【模板】网络最大流

EK算法

维护残留网络，使用 while 循环，每次循环进行以下操作：

找增广路径（BFS即可）
更新残留网络

设增广路径的流量为$k$，则将正向边的容量减去$k$，反向边的容量加上$k$

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=205,M=10005;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll n,m,S,T;
//点数，边数，源点，汇点
ll h[N],to[M],ne[M],f[M],idx;
//链式前向星，下标从0开始，01，23...存正反边，i^1即为第i条边的反向边，h初始为-1
//f[i]表示第i条边的容量（即c(u,v)）
ll d[N],pre[N];
//d[i]表示第i个点的最大流量，pre数组记录找到的增广路径中每个点对应的前一条边
bool st[N];
//bfs判断是否入队

void add(ll a,ll b,ll c){
    to[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    to[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}//加正反两条边

bool bfs(){
    queue<ll>q;
    memset(st,false,sizeof st);
    q.push(S);
    st[S]=true,d[S]=INF;
    while(!q.empty()){
        ll t=q.front();
        q.pop();
        for(ll i=h[t];~i;i=ne[i]){
            ll ver=to[i];
            if(!st[ver]&&f[i]){
                st[ver]=true;
                d[ver]=min(d[t],f[i]);
                pre[ver]=i;
                if(ver==T)return true;
                q.push(ver);
            }
        }
    }
    return false;
}//bfs找增广路径

ll EK(){
    ll r=0;//记录总的流量
    while(bfs()){
        r+=d[T];
        for(ll i=T;i!=S;i=to[pre[i]^1]){
            f[pre[i]]-=d[T],f[pre[i]^1]+=d[T];//更新残留网络，通过找连向当前点的边的反向边找到上一个点
        }
    }
    return r;
}//EK算法

int main(){
    cin >> n >> m >> S >> T;
    memset(h,-1,sizeof h);
    while(m--){
        ll a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    
    cout << EK() << endl;
    
    return 0;
}

时间复杂度$O(nm^2)$

Dinic算法

优化思想：每次增广时把所有可以增广的边都枚举一遍。

由于图中可能有环，因此使用分层图的思想。每个点的层数就是这个点到起点的距离，具体地，从起点开始进行 BFS ，第一次遍历到一个点时记录即可。找增广路时，规定在分层图中每次只能向层数更深的点进行遍历，即可找出增广路径。

形式化流程：

进行BFS，建立分层图
进行DFS，找出所有能增广的路径

当前弧优化：

注意到如果我们已经访问过了一条边(即把这条边的流量耗尽了），那我们以后就不用再访问这条边了。于是我们考虑开一个数组$cur$表示当前考虑到了哪一条弧。每次重新 BFS 就把$cur[x]$设为$x$邻接表中的第一个元素。而 DFS 到这个点的时候就从$cur[x]$ 开始遍历后面的边。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e4+5,M=2e5+5;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll n,m,S,T;
ll h[N],to[M],f[M],ne[M],idx;
ll d[N],cur[N];
//d:分层图层数 cur:当前弧优化
void add(ll a,ll b,ll c){
    to[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    to[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}

bool bfs(){
    queue<ll>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        ll t=q.front();
        q.pop();
        for(ll i=h[t];~i;i=ne[i]){
            ll ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;//记录层数
                cur[ver]=h[ver];//初始化当前弧
                if(ver==T)return true;
                q.push(ver);
            }
        }
    }
    return false;
}

ll find(ll u,ll limit){//表示从源点走到u，可以流过的最大流量为limit
    if(u==T)return limit;
    ll flow=0;
    for(ll i=cur[u];~i&&flow<limit;i=ne[i]){//一定要加上flow<limit，防止错误
        cur[u]=i;//流到的当前边，表示前面的边都被用完了，记录当前弧
        ll ver=to[i];
        if(d[ver]==d[u]+1&&f[i]){
            ll t=find(ver,min(f[i],limit-flow));
            if(!t)d[ver]=-1;//流不到，从图中删除
            f[i]-=t,f[i^1]+=t,flow+=t;
        }
    }
    return flow;
}

ll dinic(){
    ll r=0,flow;
    while(bfs()){//判断是否有增广路，建立分层图，初始化当前弧
        while(flow=find(S,INF)){//从源点开始找出所有的增广路
            r+=flow;
        }
    }
    return r;
}

int main(){
    cin >> n >> m >> S >> T;
    memset(h,-1,sizeof h);
    while(m--){
        ll a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    
    cout << dinic() << endl;
    
    return 0;
}

时间复杂度$O(n^2m)$

思想

要保证原问题的可行解与建立的流网络的可行流可以一一对应，这样原问题的最大值就等价于流网络中的最大可行流。

二分图匹配

例题1：洛谷P2756 飞行员配对方案问题：网络流实现二分图

飞行员配对方案问题
题目背景
第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

题目描述
一共有 $n$ 个飞行员，其中有 $m$ 个外籍飞行员和 $(n - m)$ 个英国飞行员，外籍飞行员从 $1$ 到 $m$ 编号，英国飞行员从 $m + 1$ 到 $n$ 编号。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入格式
输入的第一行是用空格隔开的两个正整数，分别代表外籍飞行员的个数 $m$ 和飞行员总数 $n$。
从第二行起到倒数第二行，每行有两个整数 $u, v$，代表外籍飞行员 $u$ 可以和英国飞行员 $v$ 配合。
输入的最后一行保证为 -1 -1，代表输入结束。

输出格式
本题存在 Special Judge。
请输出能派出最多的飞机数量，并给出一种可行的方案。
输出的第一行是一个整数，代表一次能派出的最多飞机数量，设这个整数是 $k$。
第 $2$ 行到第 $k + 1$ 行，每行输出两个整数 $u, v$，代表在你给出的方案中，外籍飞行员 $u$ 和英国飞行员 $v$ 配合。这 $k$ 行的 $u$ 与 $v$ 应该互不相同。

样例 #1
样例输入 #1
1
2
3
4
5
6
7
8
9
10
11
12
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
样例输出 #1
1
2
3
4
5
4
1 7
2 9
3 8
5 10
提示
【数据范围与约定】

对于 $100%$ 的数据，保证 $1 \leq m \leq n < 100$，$1 \leq u \leq m < v \leq n$，同一组配对关系只会给出一次。

【提示】

请注意输入的第一行先读入 $m$，再读入 $n$。

分析：

由于每个外籍飞行员只能选一次，因此从源点向每个外籍飞行员连一条容量为1的边，同理从每个英国飞行员向汇点连一条容量为1的边，对于每一对可以配对的飞行员在他们之间连一条容量为1的边，直接求最大流即可。

通过模拟可以发现，求二分图用的匈牙利算法与EK算法相同，因此使用Dinic算法可以优化时间复杂度。

输出边时可以枚举所有中间的正向边，若容量为0，则输出这条边。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+5,M=10005,INF=0x3f3f3f3f;

int n,m,S,T;
int h[N],to[M],ne[M],f[M],idx;
int d[N],cur[N];

void add(int a,int b){
    to[idx]=b,ne[idx]=h[a],f[idx]=1,h[a]=idx++;
    to[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}

bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        int t=q.front();
        q.pop();
        cur[t]=h[t];
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(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]){
        int ver=to[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i]){
            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(){
    memset(h,-1,sizeof h);
    cin >> m >> n;
    S=0,T=n+1;
    for(int i=1;i<=m;i++){
        add(S,i);
    }
    for(int i=m+1;i<=n;i++){
        add(i,T);
    }
    while(true){
        int a,b;
        cin >> a >> b;
        if(a==-1&&b==-1)break;
        add(a,b);
    }
    
    cout << dinic() << endl;
    
    for(int i=1;i<=m;i++){
        for(int j=h[i];~j;j=ne[j]){
            if(f[j]==0&&j%2==0)cout << i << ' ' << to[j] << endl;
        }
    }
    /*
    另一种方法：
    for(int i=0;i<idx;i+=2){
        if(to[i]>m&&to[i]<=n&&f[i]==0)cout << to[i^1] << ' ' << to[i] << endl;
    }
    */
    return 0;
}

例题2：洛谷P3254 圆桌问题：二分图多重匹配

圆桌问题
题目描述
有来自 $m$ 个不同单位的代表参加一次国际会议。第 $i$ 个单位派出了 $r_i$ 个代表。

会议的餐厅共有 $n$ 张餐桌，第 $i$ 张餐桌可容纳 $c_i$ 个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

输入格式
输入的第一行是用空格隔开的两个整数，分别代表单位的个数 $m$ 和餐桌的个数 $n$。
第二行有 $m$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 个单位的代表人数 $r_i$。
第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 张餐桌能容纳的人数 $c_i$。

输出格式
本题存在 Special Judge。
请输出是否存在满足要求的就餐方案，若存在，请给出任意一种可行的方案。
输出的第一行是一个非 $0$ 即 $1$ 的整数，若存在方案则输出 $1$，否则输出 $0$。
若存在方案，则对于第 $2$ 到第 $(m + 1)$ 行，在第 $(i + 1)$ 行输出 $r_i$ 个整数，代表第 $i$ 个单位的代表就餐的餐桌编号。

样例 #1
样例输入 #1
1
2
3
>4 5
>4 5 3 5
>3 5 2 6 4
样例输出 #1
1
2
3
4
5
>1
>1 2 4 5
>1 2 3 4 5
>2 4 5
>1 2 3 4 5
提示
【数据规模与约定】

对于 $100%$ 的数据，保证 $1 \leq m \leq 150$，$1 \leq n \leq 270$，$1 \leq r_i, c_i \leq 10^3$。

【提示】

请注意输入的第一行先读入 $m$ 再读入 $n$。

分析：

从源点向每个单位连一条容量为单位人数的边，从每个圆桌向汇点连一条容量为餐桌容量的边，每个单位和每个圆桌之间连一条容量为1的边。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+5,M=1e5+5,INF=0x3f3f3f3f;

int n,m,S,T;
int h[N],to[M],ne[M],f[M],idx;
int d[N],cur[N];
int tot;

void add(int a,int b,int c){
    to[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
    to[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}

bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        int t=q.front();
        q.pop();
        cur[t]=h[t];
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(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]){
        int ver=to[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i]){
            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(){
    memset(h,-1,sizeof h);
    cin >> m >> n;
    n+=m;
    S=0,T=n+1;
    for(int i=1;i<=m;i++){
        int t;
        cin >> t;
        tot+=t;
        add(S,i,t);
    }
    for(int i=m+1;i<=n;i++){
        int t;
        cin >> t;
        add(i,T,t);
    }
    for(int i=1;i<=m;i++){
        for(int j=m+1;j<=n;j++){
            add(i,j,1);
        }
    }
    if(dinic()==tot){
        cout << 1 << endl;
        for(int i=1;i<=m;i++){
            for(int j=h[i];~j;j=ne[j]){
                if(f[j]==0&&j%2==0)cout << to[j]-m << ' ';
            }
            cout << endl;
        }
    }
    else{
        cout << 0 << endl;
    }
    return 0;
}

上下界可行流

无源汇上下界可行流

题目：洛谷U409413 无源汇上下界可行流

无源汇上下界可行流
题目描述
给定一个包含 $ n $ 个点 $ m $ 条边的有向图，每条边都有一个流量下界和流量上界。

求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

输入格式
第一行包含两个整数 $ n $ 和 $ m $。

接下来 $ m $ 行，每行包含四个整数 $ a,b,c,d $ 表示点 $ a $ 和 $ b $ 之间存在一条有向边，该边的流量下界为 $ c $，流量上界为 $ d $。

点编号从 $ 1 $ 到 $ n $。

输出格式
如果存在可行方案，则第一行输出 YES，接下来 $ m $ 行，每行输出一个整数，其中第 $ i $ 行的整数表示输入的第 $ i $ 条边的流量。

如果不存在可行方案，直接输出一行 NO。

如果可行方案不唯一，则输出任意一种方案即可。

样例 #1
样例输入 #1
1
2
3
4
5
6
7
4 6
1 2 1 3
2 3 1 3
3 4 1 3
4 1 1 3
1 3 1 3
4 2 1 3
样例输出 #1
1
2
3
4
5
6
7
YES
1
2
3
2
1
1
样例 #2
样例输入 #2
1
2
3
4
5
6
7
4 6
1 2 1 2
2 3 1 2
3 4 1 2
4 1 1 2
1 3 1 2
4 2 1 2
样例输出 #2
1
NO
提示
数据范围
$ 1 \le n \le 200 $,
$ 1 \le m \le 10200 $,
$ 1 \le a,b \le n $,
$ 0 \le c \le d \le 10000 $

满足每条边的流量在上下界之间，即$c_l(u,v) \le f(u,v) \le c_u(u,v)$。

设原网络$G$有可行流$f$，要把$(G,f)$变为$(G’,f’)$。

可以把原式转为$0 \le f(u,v)-c_l(u,v) \le c_u(u,v)-c_l(u,v)$，这样容量限制即可满足，但是流量守恒不一定满足。

设$c_入=\sum_{v \in V}c_l(v,x)$，$c_出=\sum_{v \in V}c_l(x,v)$，分别表示少进的流量和少出的流量，则增加流入$c_入-c_出$即可满足流量守恒，具体地，若$c_入-c_出>0$，则从源点向当前点连一条容量为$c_入-c_出$的边，否则从当前点向汇点连一条容量为$c_出-c_入$的边。

具体步骤：

将可行流中所有边上的流量量减去流量下界，令新网络的容量变为流量上界减去流量下界
求新流网络中的最大流
将求出的可行流的边的流量加上流量下界

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=205,M=3e4+5,INF=0x3f3f3f3f;

int n,m,S,T;
int h[N],to[M],ne[M],f[M],l[M],idx;
int d[N],cur[N],A[M];
//A:表示每个点c入-c出

void add(int a,int b,int c,int d){
    to[idx]=b,ne[idx]=h[a],f[idx]=d-c,l[idx]=c,h[a]=idx++;
    to[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}

bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        int t=q.front();
        q.pop();
        cur[t]=h[t];
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(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]){
        int ver=to[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i]){
            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(){
    memset(h,-1,sizeof h);
    cin >> n >> m;
    S=0,T=n+1;
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin >> 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)cout << "NO\n";
    else{
        cout << "YES\n";
        for(int i=0;i<m*2;i+=2){
            cout << f[i^1]+l[i] << endl;//注意f[i^1]才是实际流量
        }
    }
    return 0;
}

有源汇上下界最大/最小流

在无源汇上下界可行流的基础上增加了两个限制：有源点和汇点，求最大可行流。

首先考虑第一个限制，有源点和汇点，则可以从汇点向源点连一条容量为正无穷的边，这样原图转化为无源汇的图。

再考虑第二个限制，对于原图$G$的一个可行流$f_0$，可以将$(G,f_0)$变为新图$(G’,f_0’)$，在新流的残留网络$G’{f_0’}$中存在从$s$到$t$（原图的源点和汇点）流的量，也就是之前增加的从$t$到$s$的虚边的流量，记作$f’{0,s \to t}$。在$s$到$t$中任取一个可行流$f’{s \to t}$，可以发现，原图$G$的每一个答案对应一个$|f’{0,s \to t}+f’{s \to t}|$，而$|f’{0,s \to t}+f’{s \to t}|=|f’{0,s \to t}|+|f’{s \to t}|$，其中$|f’{0,s \to t}|$是固定的，因此只需$|f’_{s \to t}|$最大/最小即可。最大直接求即可，而最小等价于求$t$到$s$的最大流。

有源汇上下界最大流

#include<bits/stdc++.h>
using namespace std;

const int N=205,M=3e4+5,INF=0x3f3f3f3f;

int n,m,S,T,s,t;
int h[N],to[M],ne[M],f[M],idx;
int d[N],cur[N],A[M];

void add(int a,int b,int c,int d){
    to[idx]=b,ne[idx]=h[a],f[idx]=d-c,h[a]=idx++;
    to[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}

bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        int t=q.front();
        q.pop();
        cur[t]=h[t];
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(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]){
        int ver=to[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i]){
            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(){
    memset(h,-1,sizeof h);
    cin >> n >> m >> s >> t;
    S=0,T=n+1;
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin >> 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]);
    }
    add(t,s,0,INF);//增加虚边，转化成无源汇图
    if(dinic()<tot)cout << "No Solution\n";
    else{
        int res=f[idx-1];//f'_{0,s -> t}
        S=s,T=t;
        f[idx-1]=f[idx-2]=0;
        cout << dinic()+res;
    }
    return 0;
}

有源汇上下界最小流

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+5,M=5e5+5,INF=2147483647;

int n,m,S,T,s,t;
int h[N],to[M],ne[M],f[M],idx;
int d[N],cur[N],A[M];

void add(int a,int b,int c,int d){
    to[idx]=b,ne[idx]=h[a],f[idx]=d-c,h[a]=idx++;
    to[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}

bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        int t=q.front();
        q.pop();
        cur[t]=h[t];
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(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]){
        int ver=to[i];
        cur[u]=i;
        if(d[ver]==d[u]+1&&f[i]){
            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(){
    memset(h,-1,sizeof h);
    cin >> n >> m >> s >> t;
    S=0,T=n+1;
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin >> 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]);
    }
    add(t,s,0,INF);
    if(dinic()<tot)cout << "No Solution\n";
    else{
        int res=f[idx-1];
        S=t,T=s;//不同点1:求t到s的最大流
        f[idx-1]=f[idx-2]=0;
        cout << res-dinic();//不同点2:由于t到s的最大流为负数，所以是减去(f_{s->t}=-f_{t->s}))
    }
    return 0;
}

多源汇最大流

有多个源点和汇点，直接建立一个超级源点和一个超级汇点，从超级源点向每个源点连出一条容量为正无穷的边，从每个汇点向超级汇点连出一个容量为正无穷的边即可。

题目：U409708 多源汇最大流

多源汇最大流
题目描述
给定一个包含 $ n $ 个点 $ m $ 条边的有向图，并给定每条边的容量，边的容量非负。

其中有 $ S_c $ 个源点，$ T_c $ 个汇点。

图中可能存在重边和自环。

求整个网络的最大流。

输入格式
第一行包含四个整数 $ n,m,S_c,T_c $。

第二行包含 $ S_c $ 个整数，表示所有源点的编号。

第三行包含 $ T_c $ 个整数，表示所有汇点的编号。

接下来 $ m $ 行，每行三个整数 $ u,v,c $，表示从点 $ u $ 到点 $ v $ 存在一条有向边，容量为 $ c $。

点的编号从 $ 1 $ 到 $ n $。

输出格式
输出一个整数表示整个网络的最大流。

样例 #1
样例输入 #1
1
2
3
4
5
6
7
8
4 5 2 2
2 4
1 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
样例输出 #1
1
70
提示
数据范围
$ 2 \le n \le 10000 $,
$ 1 \le m \le 10^5 $,
$ 0 \le c \le 10000 $,
保证源点集合和汇点集合没有交集。

#include<bits/stdc++.h>
using namespace std;

const int N=1e4+5,M=3e5+5,INF=0x3f3f3f3f;

int n,m,S,T;
int h[N],to[M],f[M],ne[M],idx;
int d[N],cur[N];

void add(int a,int b,int c){
    to[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    to[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}

bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(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=to[i];
        if(d[ver]==d[u]+1&&f[i]){
            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(){
    int sc,tc;
    cin >> n >> m >> sc >> tc;
    memset(h,-1,sizeof h);
    S=0,T=n+1;
    for(int i=1;i<=sc;i++){
        int x;
        cin >> x;
        add(S,x,INF);
    }
    for(int i=1;i<=tc;i++){
        int x;
        cin >> x;
        add(x,T,INF);
    }
    
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    
    cout << dinic() << endl;
    return 0;
}

关键边

关键边：当增加这条边的容量时网络流的最大流会增加。

当求出一个网络流的最大可行流时，不难看出只有当一条边的流量等于流量时，即$f(u,v)=c(u,v)$时，这条边才有可能成为关键边，并且需要在图$G_f$中存在$s \to u$和$v \to t$的路径时这条边才是关键边。

具体做法：

求出原图的一个最大可行流
在残留网络中求出所有源点能到的点，从汇点反向搜索能反向到达的边
枚举所有边，判断是否满足要求

例题：洛谷U409910 伊基的故事 I - 道路重建

#include<bits/stdc++.h>
using namespace std;

const int N=505,M=1e4+5,INF=0x3f3f3f3f;

int n,m,S,T;
int h[N],to[M],f[M],ne[M],idx;
int d[N],cur[N];
bool vis_s[N],vis_t[N];


void add(int a,int b,int c){
    to[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
    to[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}

bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(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=to[i];
        if(d[ver]==d[u]+1&&f[i]){
            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;
}

void dfs(int u,bool st[],int t){
    st[u]=true;
    for(int i=h[u];~i;i=ne[i]){
        int j=i^t,ver=to[i];
        if(f[j]&&!st[ver]){
            dfs(ver,st,t);
        }
    }
}

int main(){
    cin >> n >> m;
    S=0,T=n-1;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    
    dinic();
    dfs(S,vis_s,0);
    dfs(T,vis_t,1);
    
    int res=0;
    for(int i=0;i<m*2;i+=2){
        if(!f[i]&&vis_s[to[i^1]]&&vis_t[to[i]]){
            res++;
        }
    }
    cout << res;
    return 0;
}

最小割

由于任意的$|f|\le c(S,T)$，即流小于等于割，因此一定存在最大流等于最小割，直接求最大流即可。

#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize(2)


const int N=1e4+5,M=2e5+5,INF=0x3f3f3f3f;
int n,m,S,T;

int h[N],ne[M],to[M],f[M],idx;

int d[N],cur[N];

void add(int a,int b,int c){
    to[idx]=b,ne[idx]=h[a],f[idx]=c,h[a]=idx++;
    to[idx]=a,ne[idx]=h[b],f[idx]=0,h[b]=idx++;
}

bool bfs(){
    queue<int>q;
    memset(d,-1,sizeof d);
    q.push(S),d[S]=0,cur[S]=h[S];
    while(!q.empty()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(d[ver]==-1&&f[i]){
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)return true;
                q.push(ver);
            }
        }
    }
    return false;
}

int find(int u,int limit){
    if(u==T)return limit;
    int flow=0;
    for(int i=h[u];~i&&flow<limit;i=ne[i]){
        cur[u]=i;
        int ver=to[i];
        if(d[ver]==d[u]+1&&f[i]){
            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 res=0,flow;
    while(bfs()){
        while(flow=find(S,INF))res+=flow;
    }
    return res;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m >> S >> T;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    
    cout << dinic();
    return 0;
}

费用流

一种实现思路：把EK算法的bfs换成SPFA即可。

模板：最小费用最大流

#include<bits/stdc++.h>
using namespace std;

const int N=5005,M=1e5+5,INF=0x3f3f3f3f;

int n,m,S,T;

int h[N],ne[M],to[M],f[M],w[M],idx;
int d[N],pre[N],incf[N];

bool st[N];

void add(int a,int b,int c,int d){
    to[idx]=b,ne[idx]=h[a],f[idx]=c,w[idx]=d,h[a]=idx++;
    to[idx]=a,ne[idx]=h[b],f[idx]=0,w[idx]=-d,h[b]=idx++;
}

bool spfa(){
    queue<int>q;
    memset(d,0x3f,sizeof d);
    incf[T]=0;
    q.push(S),d[S]=0,incf[S]=INF;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];~i;i=ne[i]){
            int ver=to[i];
            if(f[i]&&d[ver]>d[t]+w[i]){
                d[ver]=d[t]+w[i];
                pre[ver]=i;
                incf[ver]=min(f[i],incf[t]);
                if(!st[ver]){
                    q.push(ver);
                    st[ver]=true;
                }
            }
        }
    }
    
    return incf[T]>0;
}

void EK(int &flow,int &cost){
    flow=cost=0;
    while(spfa()){
        int t=incf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=to[pre[i]^1]){
            f[pre[i]]-=t;
            f[pre[i]^1]+=t;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof h);
    cin >> n >> m >> S >> T;
    for(int i=1;i<=m;i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        add(a,b,c,d);
    }
    
    int flow,cost;
    EK(flow,cost);
    cout << flow << ' ' << cost << endl;
    
    return 0;
}

注意：这种算法无法处理存在负环的情况

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。