网络流学习笔记

引言想象一个自来水管道网络有一座水厂源点一个居民区汇点中间有各种管道边每条管道有最大输水容量容量。问在不超出任何管道容量的前提下水厂最多能向居民区输送多少水这就是最大流问题。网络流问题的形式化描述来自图论给定有向图每条边有容量求从源点 s 到汇点 t 的最大可行流量。它不仅有直接的现实应用交通、电力、通信网络还能通过巧妙的模型转化解决二分图匹配、任务分配、最小路径覆盖、图像分割等看似无关的问题。如果把普通图遍历比作“走迷宫”那么网络流就是“水往低处流但找对路径就能逆天改命”—— 它通过不断寻找增广路反复调整流量分配最终达到全局最优。前置知识有向图边有方向流量只能沿方向传输。容量Capacity边能通过的最大流量。流量Flow实际通过边的流量不能超过容量。源点Source只流出不流入的点。汇点Sink只流入不流出的点。残量网络Residual Network在原图基础上为每条边添加一条反向边容量等于当前已用流量表示“可以退回”的流量。增广路Augmenting Path在残量网络中从源到汇的一条路径沿该路径可以增加流量。最大流最小割定理最大流的值等于最小割的容量。割将点集划分为包含源点和不包含源点的两部分割的容量为从源侧到汇侧的边容量和。核心思想求解最大流的经典算法基于增广路思想从零流量开始。不断在残量网络中找到一条从源到汇的路径增广路并尽可能增加流量。当找不到增广路时当前流量即为最大流。Ford-Fulkerson 方法基础每次用 DFS 或 BFS 找一条增广路沿路增加流量流量等于路径上最小残量。复杂度 O(E * maxFlow)可能很慢。Edmonds-Karp 算法BFS 实现使用 BFS 找最短增广路按边数复杂度 O(V * E²)稳定但较慢。Dinic 算法最常用引入分层图Level Graph和当前弧优化多次 BFS 分层 多次 DFS 增广复杂度 O(V² * E) 或对于单位容量图 O(min(V^{2/3}, E^{1/2}) * E)实际非常快。Dinic 核心步骤BFS从源点开始给每个点标上层次到源点的距离构建分层图只走层次递增的边。DFS在分层图上寻找增广路一次 DFS 可以找到多条使用当前弧优化跳过已经试过的边。重复 BFSDFS直到 BFS 无法到达汇点。形象比喻BFS 像是绘制一张“高度地图”只有向上爬层次增加才能前进DFS 则是派出多批探险队一次性探索所有可行路径。当前弧优化记录每个节点下一次该试哪条边避免重复劳动。算法步骤与代码框架Dinicstruct Dinic { struct Edge { int to, rev; // rev: 反向边在邻接表中的下标 long long cap; }; vectorvectorEdge g; vectorint level, iter; // level: 层次, iter: 当前弧 int n; Dinic(int n) : n(n), g(n), level(n), iter(n) {} void add_edge(int from, int to, long long cap) { g[from].push_back({to, (int)g[to].size(), cap}); g[to].push_back({from, (int)g[from].size()-1, 0}); // 反向边容量为0 } void bfs(int s) { fill(level.begin(), level.end(), -1); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int v q.front(); q.pop(); for (auto e : g[v]) { if (e.cap 0 level[e.to] 0) { level[e.to] level[v] 1; q.push(e.to); } } } } long long dfs(int v, int t, long long f) { if (v t) return f; for (int i iter[v]; i (int)g[v].size(); i) { Edge e g[v][i]; if (e.cap 0 level[v] level[e.to]) { long long d dfs(e.to, t, min(f, e.cap)); if (d 0) { e.cap - d; g[e.to][e.rev].cap d; return d; } } } return 0; } long long max_flow(int s, int t) { long long flow 0; while (true) { bfs(s); if (level[t] 0) return flow; fill(iter.begin(), iter.end(), 0); long long f; while ((f dfs(s, t, 1e18)) 0) { flow f; } } } };复杂度与性质算法时间复杂度适用场景Ford-Fulkerson (DFS)O(E * maxFlow)容量较小或整数Edmonds-Karp (BFS)O(V * E²)稳定但慢Dinic (分层多路增广)O(V² * E) 实际快很多绝大多数题目ISAP (Improved SAP)O(V² * E) 略优于 Dinic高级选手重要性质整数容量最大流值一定是整数且算法在有限步内结束。最小割最大流结束后从源点 BFS 能到达的点集与不能到达的点集构成一个最小割。多源多汇可以添加超级源点和超级汇点转化为单源单汇。无向边可以拆成两个方向各容量为 c 的有向边。例题与解析例题1最大流模板题Luogu P3376题目描述给定 n 个点m 条有向边每条边有容量求从源点 s 到汇点 t 的最大流。输入示例4 5 1 4 1 2 30 1 3 20 2 3 20 2 4 20 3 4 30输出示例50解题思路直接使用 Dinic 算法套用上面代码模板即可。解析注意点数可达 10^5边数可达 10^5 时Dinic 的 O(V²E) 理论复杂度会超时但实际常数小且数据通常不会卡到最坏情况。更优选择是 ISAP 或 HLPP。但模板题 P3376 用 Dinic 即可通过。例题2二分图最大匹配Luogu P3386题目描述给定二分图左部有 n1 个点右部有 n2 个点以及 m 条边。求最大匹配数即最多能配成多少对使得每条边连接左右且不共用点。输入示例3 3 3 1 1 1 2 2 3输出示例2解题思路建立超级源点 S 连接所有左部点容量为 1。左部点与原边连接右部点容量为 1。所有右部点连接超级汇点 T容量为 1。最大流即为最大匹配数。解析因为每个左点只能匹配一个右点容量1右点也只能被匹配一次容量1所以最大流限制了一对一关系。该模型也可用于二分图多重匹配将容量改为更大值。例题3最小路径覆盖Luogu P2764题目描述给定有向无环图DAG求最少的路径数使得每条路径覆盖所有点路径之间点不重叠路径方向沿有向边。输入示例11 11 1 2 1 3 2 4 3 5 4 6 5 6 6 7 7 8 8 9 9 10 10 11输出示例3解题思路将每个点 i 拆成左点 i 和右点 i。对于原图每条边 u→v连接左 u 到右 v容量为 1。超级源点连所有左点超级汇点连所有右点容量为 1。最大匹配 可以合并的边数即可以节省的路径条数。最小路径覆盖 点数 - 最大匹配数。解析每条路径除了起点外每个点有唯一的前驱除了终点外每个点有唯一的后继。拆点后一条匹配边 u→v 表示原图中 u 和 v 可以在同一条路径上相邻。最大匹配最大化这种相邻关系从而最小化路径数。拓展最小费用最大流每条边除了容量还有单位费用求在最大流前提下的最小总费用SPFA 或 Dijkstra 势能。上下界网络流每条边有最小流量和最大流量约束。节点容量可将点拆成入点和出点之间连容量为节点容量的边。平面图最大流可转化为对偶图最短路。刷题题单建议网络流24题