当前位置：首页 > news >正文

网络最大流学习笔记

news 2026/3/27 0:58:08

「引入」

什么是网络流？你可以理解为：有一个管道系统，有一个源点 \(S\) 和一个汇点 \(T\) 。系统里有许多带容量的管道。从 \(S\) 到 \(T\) 的一条路径叫增广路，这条路上剩余容量最小的管道，决定了这条路最多能流多少，这个值就是这条增广路的流量。整个网络中所有合法流量的总和，就是网络流；能流的最大总量，就是最大流。

「基础」

基本定义

残量网络：由所有节点，以及所有 \(c-f\ge 0\) 的正向边和所有反向边构成的网络叫做残量网络。
增广路：残量网络中，从 \(S\) 到 \(T\) 的一条路径叫增广路。
容量：\(c(x,y)\) 表示从 \(x\) 到 \(y\) 的边最多能装多少。
流量：类似于容量，\(f(x,y)\) 表示从 \(x\) 到 \(y\) 的边目前装了多少。

反向边

反向边是网络流中至关重要的一环。

为什么要建反向边？因为可能会出现一条边被多个增广路所选择的情况，建反向边相当于是给了程序一次反悔的机会。

简单来说，当我们给正向边 \(x→y\) 分配了流量 \(f(x,y)\) 后，会自动建立一条反向边 \(y→x\)，它的容量就是当前正向边的流量 \(f(x,y)\)（代表最多能反悔多少流量）。

「例题」

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

给出一个网络图，以及其源点和汇点，求出其网络最大流，其中，\(1 \leq n\leq200\)，\(1 \leq m\leq 5000\)，\(0 \leq w\lt 2^{31}\)。

Edmonds−Karp 算法

讲完基础的就该讲算法了，先来讲 Edmonds−Karp 算法（下文简称 EK）。

EK 的核心思想就是用 BFS 不断寻找增广路并更新答案，直到没有增广路可找（对，这算法很暴力）。

怎样用 BFS 找增广路？

tips：下文用残量表示 \(c-f\) 的差（即该边剩余的容量）。

首先我们每次在残量网络中跑 BFS：

从源点 \(S\) 出发，走残量 \(\ne 0\) 的边。
记录每个点的前驱。
如果搜到了汇点 \(T\) ，就说明找到了一条增广路。

找到增广路后怎么做？

从 \(T\) 沿着之前记录的前驱往回走，找到这条增广路中最小的残量，这便是该增广路的流量。
再沿着这条路，把所有正向边的残量减去流量，反向边加上流量。
把流量累加到答案中。

随后重复以上的步骤，直到找不到增广路为止。

Edmonds−Karp 算法实现

Tips：十年OI一场空，不开________见祖宗。

#include<bits/stdc++.h>
#define int long long // 注意到w<2^31，所以开long long
using namespace std;
const int INF=1e18+5;
int n,m,s,t;
struct node{int to,c,rev; // to=终点，c=残量，rev=反向边下标
};
vector<node> g[210];
int p[210],pe[210],flow[210]; // p_v表示到达v的前驱，pe_v表示到达v的前驱边下标，flow_v表示到v路径的最小残量
void add(int u,int v,int w){ // 加边g[u].push_back({v,w,(int)g[v].size()});g[v].push_back({u,0,(int)g[u].size()-1}); // 建反向边
}
int bfs(int s,int t){ // Edmonds−Karp算法int maxn=0;while(1){memset(p,-1,sizeof(p)); // -1表示未访问memset(flow,0,sizeof(flow)); // 初始化为0queue<int> q;q.push(s);flow[s]=INF;while(!q.empty()){int u=q.front();q.pop();int i=0;for(auto e:g[u]){if(e.c!=0&&p[e.to]==-1){ // 残量不为0且未访问过p[e.to]=u; // 记录前驱点pe[e.to]=i; // 记录前驱边下标flow[e.to]=min(flow[u],e.c); // 更新残量q.push(e.to);if(e.to==t) goto be; // 如果到达汇点就退出循环}i++;}}be:if(p[t]==-1) break; // 如果没到汇点，说明已经没有增广路可找，退出循环int now=t;while(now!=s){ // 更新残量网络int u=p[now],i=pe[now];auto &e=g[u][i];e.c-=flow[t];g[now][e.rev].c+=flow[t];now=u;}maxn+=flow[t]; // 累加流量}return maxn;
}
signed main(){cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}cout<<bfs(s,t);return 0;
}

时间复杂度 \(O(nm^2)\)，略高。

Dinic 算法

Edmonds−Karp 算法的优点有很多，比如好理解、好实现等，但缺点也很明显，时间复杂度太高了 。这就引出了我们下文的主人公，Dinic 算法。

Dinic 算法的核心思想是先跑 BFS 残量网络构造成一张分层图，然后跑 DFS 一次性找多条增广路的流量，避免了 EK 瞎跑的问题，效率也更高，时间复杂度能降至 \(O(n^2m)\)。

什么是分层图

我们给残量网络中的每个点标上「层数」：

源点 \(S\) 为 \(0\) 层。
从层数为 \(k\) 的点走到的下一个未被标层的点，该点便为 \(k+1\) 层。
汇点 \(T\) 必须有层数，否则就说明没有增广路。

你可以把分层图理解为一层层台阶，并且这个台阶只能向上（走向 \(k+1\) 层），不能向下（走向 \(k-1\) 层）。

BFS 构建分层图

这一步跟 EK 的 BFS 差不多，只不过多了标层的步骤：

从源点 \(S\) 出发，走残量 \(\ne 0\) 的边。
给每个点标层数。
如果跑完 BFS 后 \(T\) 没有被标层，说明没有增广路，算法结束。

DFS 找流量

用 DFS 从 \(S\) 跑到 \(T\) ：

类似于 EF，记录每个点的最小残量。
找到一条增广路后，回溯找下一条。
把流量累加到答案中。

然后重复这两步即可。

Dinic 算法实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18+5;
int n,m,s,t;
struct node{int to,c,rev; // 和EK一致：终点、残量、反向边下标
};
vector<node> g[210];
int dist[210]; // 分层图：记录每个点的层数
int cur[210];  // 当前弧优化：记录每个点遍历到的边下标
// 加边函数和EK完全复用，不用改
void add(int u,int v,int w){g[u].push_back({v,w,(int)g[v].size()});g[v].push_back({u,0,(int)g[u].size()-1});
}
// 第一步：BFS构建分层图
bool bfs(){memset(dist,-1,sizeof(dist)); // -1表示未标层queue<int> q;q.push(s);dist[s]=0;cur[s]=0; // 源点当前弧初始化为0while(!q.empty()){int u=q.front();q.pop();for(auto e:g[u]){if(e.c!=0 && dist[e.to]==-1){ // 残量≠0且未标层dist[e.to]=dist[u]+1; // 层数+1cur[e.to]=0; // 初始化当前弧q.push(e.to);if(e.to==t) return true; // 找到汇点，提前退出}}}return false; // 汇点不可达，无增广路
}
// 第二步：DFS找阻塞流（u=当前点，limit=当前路径最小残量）
int dfs(int u,int limit){if(u==t) return limit; // 到达汇点，返回本次流量int sum=0; // 记录本次DFS的总流量// 从当前弧开始遍历，避免重复走无效边for(int i=cur[u];i<g[u].size();i++){cur[u]=i; // 更新当前弧auto &e=g[u][i];// 残量≠0 + 符合分层图（只能走向层数+1）if(e.c!=0 && dist[e.to]==dist[u]+1){int minn=dfs(e.to,min(limit-sum,e.c));if(minn>0){e.c-=minn; // 正向边减流量g[e.to][e.rev].c+=minn; // 反向边加流量sum+=minn;if(sum==limit) break; // 流量用完，剪枝退出}}}return sum;
}
// Dinic核心函数
int dinic(){int maxn=0;while(bfs()){ // 只要能构建分层图maxn+=dfs(s,INF); // 累加阻塞流}return maxn;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}cout<<dinic()<<endl;return 0;
}