机器学习模型上线后为何频繁故障？生产级MLOps实战指南
2026/6/14 6:37:59
引言
想象一个自来水管道网络：有一座水厂（源点），一个居民区（汇点），中间有各种管道（边），每条管道有最大输水容量（容量）。问：在不超出任何管道容量的前提下，水厂最多能向居民区输送多少水？这就是最大流问题。
网络流问题的形式化描述来自图论：给定有向图，每条边有容量，求从源点 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 可以找到多条），使用当前弧优化跳过已经试过的边。
重复 BFS+DFS，直到 BFS 无法到达汇点。
形象比喻：BFS 像是绘制一张“高度地图”，只有向上爬（层次增加）才能前进；DFS 则是派出多批探险队，一次性探索所有可行路径。当前弧优化记录每个节点下一次该试哪条边，避免重复劳动。
算法步骤与代码框架（Dinic）
struct Dinic { struct Edge { int to, rev; // rev: 反向边在邻接表中的下标 long long cap; }; vector<vector<Edge>> g; vector<int> 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); queue<int> 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题