目录引入Ford-Fulkerson算法Edmonds-Karp 算法Dinic算法最大流最小割定理练习摘要本文系统介绍了最大流算法的核心概念与经典实现。首先通过物流配送网络的实际案例引入流网络模型阐述容量限制与流量守恒两大基本性质。随后详细解析了三种主流算法Ford-Fulkerson 算法基于深度优先搜索与残存网络构建反向边的增广路径思想Edmonds-Karp 算法通过广度优先搜索确保每次找到最短增广路径提升稳定性Dinic 算法结合 BFS 分层与 DFS 多路增广并引入当前弧优化显著提高效率。文章还从数学角度证明了流叠加引理并阐述了最大流最小割定理的工程意义。最后提供了完整的 C 语言实现代码链式前向星存储及一系列经典练习题为读者构建了从理论到实践的知识体系。引入配送网络采用 “中心仓 — 中转场 — 末端站点” 三级结构所有包裹从龙华中心分拣仓发出经城市中转场集散后配送至各区末端站点。每条运输线路受道路通行能力、货运班次限制存在单日最大运力上限。运营团队需在 618 大促前测算全网单日最大可配送包裹总量并定位运力瓶颈以制定备货与调度方案。源点 S龙华中心分拣仓一级中转节点A - 深圳北站中转场、B - 平湖分拣中心二级中转节点C - 银湖中转场、D - 西丽中转场末端汇点E - 南山配送站、F - 福田配送站、G - 罗湖配送站SA12SB10AC8AD9BC6BG7CF11CG5DE10DF4构建网络流。流必须要满足两个条件1容量限制。对于所有的结点要求2流量守恒。对于所有的结点要求从点A流出的流量不能超过x从点A流出多少点B就能接收多少。流的值Ford-Fulkerson算法为了解决这样的问题先尝试使用深度搜索算法从源点到汇点找出一条路径更新容量再找出一条路径重复这种操作直到无法找到路径。在更新容量的时候先尝试用原容量减去流量。很快我们发现了问题dfs寻找的路径一开始可能不是朝着最大流方向寻找的导致最大流求解错误。下图的流网络中第一次dfs后更新容量发现无法继续找到路径最大流为10但实际上最大流为20。有什么方法可以让dfs迷途知返呢当流发生更新时流中所有的路径段容量减去流的值同时构建反向边反向边的容量为流的值。这种存在反向边的网络可以称作残存网络。在残存网络中找从源点到汇点的路径就是找增广路径。我们可以发现流之间相互叠加最终构成了最大流。我们想通过数学的方式证明这一点。设为一个流网络源结点为汇点为设为中的一个流。设由流所诱导的残存网络设为中的一个流。其值为。下面引用《算法导论第三版》26.1流网络中的证明方式证明容量守恒又证明流量守恒定义为有边从源结点s到达的结点集合为有边通往s的结点集合。我们有并且因为不允许有反平行边我们有。现在来计算将v的范围全部扩展到结点集合V上有补充。增广路径为在残存网络中从源点 s 到汇点 t 的简单路径顶点不重复路径上所有边残量 0。如下图所示S为起点T为终点各段路径默认流量非0红色箭头组成路径为增广路径的是选B选项。选项A存在回路选项C存在残量为0的边选项D存在顶点重复。下面走一遍Ford-Fulkerson算法。s为源点t为汇点最大流为20。示例代码C语言、链式前向星#include stdio.h #include string.h #include stdbool.h #define MAX_VEX 100 // 最大顶点数 #define MAX_EDGE 1000 // 最大边数量正向反向边 #define INF 99999999 // 代表无穷大 // ---------- 链式前向星结构 ---------- int head[MAX_VEX]; // head[u]u节点第一条边下标 int to[MAX_EDGE]; // 边的终点 int next[MAX_EDGE]; // 下一条边 int cap[MAX_EDGE]; // 边残量 int edge_cnt; // 边计数器 // 添加边正向边 反向边残量初始0 void add_edge(int u, int v, int c) { to[edge_cnt] v; cap[edge_cnt] c; next[edge_cnt] head[u]; head[u] edge_cnt; to[edge_cnt] u; cap[edge_cnt] 0; next[edge_cnt] head[v]; head[v] edge_cnt; } bool visited[MAX_VEX]; // DFS 访问标记 /* DFS 寻找一条从 u 到 t 的增广路径 u: 当前顶点, t: 汇点, f: 流入 u 的流量上限 返回值: 找到的增广路径上的瓶颈流量 */ int dfs(int u, int t, int f) { if (u t) return f; visited[u] true; for (int e head[u]; e ! -1; e next[e]) { int v to[e]; if (!visited[v] cap[e] 0) { int bottleneck dfs(v, t, f cap[e] ? f : cap[e]); if (bottleneck gt; 0) { cap[e] - bottleneck; cap[e ^ 1] bottleneck; return bottleneck; } } } return 0; } /* Ford-Fulkerson 主算法 */ int ford_fulkerson(int s, int t) { int max_flow 0; int augment; // 逗号表达式先清空访问标记再找增广路找到增广路则进入循环累加 while (memset(visited, 0, sizeof(visited)), (augment dfs(s, t, INF)) 0) { max_flow augment; } return max_flow; } // ---------- 测试 ---------- int main() { memset(head, -1, sizeof(head)); edge_cnt 0; int s 0, v1 1, v2 2, v3 3, v4 4, t 5; add_edge(s, v1, 16); add_edge(s, v2, 13); add_edge(v1, v3, 12); add_edge(v2, v1, 4); add_edge(v2, v4, 14); add_edge(v3, v2, 9); add_edge(v3, t, 20); add_edge(v4, v3, 7); add_edge(v4, t, 4); int result ford_fulkerson(s, t); printf(最大流 Max Flow %d\n, result); // 输出 23 return 0; }Edmonds-Karp 算法FF算法在寻找增广路径的时候喜欢四处跑时间不可控。如果将DFS替换为BFS相对来说会稳定很多。示例代码C语言、链式前向星#include stdio.h #include string.h #include stdbool.h #define MAX_VEX 100 #define MAX_EDGE 1000 #define INF 99999999 // ---------- 链式前向星 ---------- int head[MAX_VEX]; int to[MAX_EDGE]; int next[MAX_EDGE]; int cap[MAX_EDGE]; int edge_cnt; // 添加正向边 反向边 void add_edge(int u, int v, int c) { to[edge_cnt] v; cap[edge_cnt] c; next[edge_cnt] head[u]; head[u] edge_cnt; to[edge_cnt] u; cap[edge_cnt] 0; next[edge_cnt] head[v]; head[v] edge_cnt; } // BFS记录前驱parent[v] (from节点, 边编号) int parent_node[MAX_VEX]; int parent_edge[MAX_VEX]; int n; // 顶点数 /* BFS 在残量网络中寻找一条从 s 到 t 的最短增广路径 返回值true 表示找到路径false 表示无路可走 */ bool bfs(int s, int t) { memset(parent_node, -1, sizeof(parent_node)); memset(parent_edge, -1, sizeof(parent_edge)); int queue[MAX_VEX]; int front 0, rear 0; queue[rear] s; parent_node[s] s; // 源点标记 while (front rear) { int u queue[front]; // 遍历u所有出边 for (int e head[u]; e ! -1; e next[e]) { int v to[e]; // 残量0 且未访问 if (parent_node[v] -1 cap[e] 0) { parent_node[v] u; parent_edge[v] e; // 记录到达v使用的边 if (v t) return true; queue[rear] v; } } } return false; } /* Edmonds-Karp 主算法 */ int edmonds_karp(int s, int t) { int max_flow 0; // 核心循环只要 BFS 能找到增广路径 while (bfs(s, t)) { // 1. 寻找瓶颈路径上的最小残量 int bottleneck INF; for (int v t; v ! s; v parent_node[v]) { int e parent_edge[v]; if (cap[e] bottleneck) { bottleneck cap[e]; } } // 2. 更新残量网络 for (int v t; v ! s; v parent_node[v]) { int e parent_edge[v]; cap[e] - bottleneck; // 正向边容量减少 cap[e ^ 1] bottleneck; // 反向边容量增加异或取反向边 } // 3. 累加最大流 max_flow bottleneck; } return max_flow; } // ---------- 测试 ---------- int main() { memset(head, -1, sizeof(head)); edge_cnt 0; int s 0, v1 1, v2 2, v3 3, v4 4, t 5; n 6; // 用到最大节点编号5总共6个节点0~5 // 建图 add_edge(s, v1, 16); // S -gt; v1 add_edge(s, v2, 13); // S -gt; v2 add_edge(v1, v3, 12); // v1 -gt; v3 add_edge(v2, v1, 4); // v2 -gt; v1 add_edge(v2, v4, 14); // v2 -gt; v4 add_edge(v3, v2, 9); // v3 -gt; v2 add_edge(v3, t, 20); // v3 -gt; t add_edge(v4, v3, 7); // v4 -gt; v3 add_edge(v4, t, 4); // v4 -gt; t int result edmonds_karp(s, t); printf(Edmonds-Karp 最大流结果: %d\n, result); // 标准答案 23 return 0; }Dinic算法EK算法找到汇点后立刻返回一条增广路然后重新DFS如果能多路增广效率就会提升很多。DFS的工作职责不再是找增广路径而是为残存网络分层分层后再通过DFS找增广路径。弧优化在朴素 Dinic 的 DFS 增广过程中每次访问一个节点时都会从头遍历该节点的所有邻接边。但在同一轮 BFS 分层周期内很多边已经失去了增广价值边的剩余容量已经耗尽无法再通过流量从这条边出发后续路径根本无法到达汇点。示例代码C语言、链式前向星#include stdio.h #include string.h #include stdbool.h #define MAXN 10005 // 最大顶点数 #define MAXM 200005 // 最大边数包含反向边 #define INF 0x3f3f3f3f // ---------- 链式前向星数据结构 ---------- int head[MAXN]; int to[MAXM]; int next[MAXM]; int cap[MAXM]; int edge_cnt; void add_edge(int u, int v, int c) { // 正向边 to[edge_cnt] v; cap[edge_cnt] c; next[edge_cnt] head[u]; head[u] edge_cnt; // 反向边初始容量为0用于退流 to[edge_cnt] u; cap[edge_cnt] 0; next[edge_cnt] head[v]; head[v] edge_cnt; } // ---------- Dinic 算法核心变量 ---------- int level[MAXN]; // 节点层次 int cur[MAXN]; // 当前弧优化指针 int queue[MAXN]; // BFS 手写队列 int n; // 总节点数 // BFS 构建分层图 bool bfs(int s, int t) { memset(level, -1, sizeof(int) * n); int front 0, rear 0; level[s] 0; queue[rear] s; while (front lt; rear) { int u queue[front]; for (int e head[u]; e ! -1; e next[e]) { int v to[e]; if (cap[e] gt; 0 amp;amp; level[v] -1) { level[v] level[u] 1; queue[rear] v; } } } return level[t] ! -1; } // DFS 多路增广一次调用推完所有可行增广路返回从u出发的总推送流量 int dfs(int u, int t, int flow) { if (u t || flow 0) return flow; int total_push 0; // 累计从当前节点推送出去的总流量 // 从当前弧开始遍历流量耗尽则提前退出 for (int *e_ptr amp;cur[u]; *e_ptr ! -1 amp;amp; flow gt; 0; *e_ptr next[*e_ptr]) { int v to[*e_ptr]; if (cap[*e_ptr] gt; 0 amp;amp; level[v] level[u] 1) { int bottleneck dfs(v, t, flow lt; cap[*e_ptr] ? flow : cap[*e_ptr]); if (bottleneck gt; 0) { // 更新残量网络 cap[*e_ptr] - bottleneck; cap[(*e_ptr) ^ 1] bottleneck; total_push bottleneck; flow - bottleneck; // 剩余可推送流量减少 } } } return total_push; } // Dinic 主算法 int dinic(int s, int t) { int max_flow 0; while (bfs(s, t)) { // 每轮分层后重置当前弧 for (int i 0; i lt; n; i) cur[i] head[i]; // 一次DFS求出本轮阻塞流直接累加 max_flow dfs(s, t, INF); } return max_flow; } // ---------- 测试 ---------- int main() { memset(head, -1, sizeof(head)); edge_cnt 0; int s 0, v1 1, v2 2, v3 3, v4 4, t 5; n 6; // 建图 add_edge(s, v1, 16); add_edge(s, v2, 13); add_edge(v1, v3, 12); add_edge(v2, v1, 4); add_edge(v2, v4, 14); add_edge(v3, v2, 9); add_edge(v3, t, 20); add_edge(v4, v3, 7); add_edge(v4, t, 4); int result dinic(s, t); printf(Dinic 最大流结果: %d\n, result); return 0; }最大流最小割定理对于一个有源点 s、汇点 t 的有向流网络若将顶点全集 V 划分为两个互不相交的子集 S 和 T满足源点在源侧汇点在汇侧划分完整则这个二元组就称为该网络的一个s-t 割。流网络G中任意流f的值不能超过G的任意切割的容量。在下图中最大流的值为23最小割的值也为23红箭头。在工程中找到最小割提升效率可以缩短工期。练习洛谷 P3376 【模板】网络最大流AcWing 2171. EK 求最大流洛谷 P2756 飞行员配对方案问题AcWing 2240. 餐饮Dining洛谷 P2764 最小路径覆盖问题洛谷 P1344 【模板】最小割AcWing 2234. 多源汇最大流洛谷 P2774 方格取数问题LeetCode LCP 04. 覆盖洛谷 P2057 [SHOI2007] 善意的投票