Ford-Fulkerson方法求最大流问题 题目描述 假设有一个有向图表示输水管道网络，其中每条边代表一根管道，边的权值表示该管道的流量上限。图中有两个特殊节点：源点（水源）和汇点（用水点）。问题要求计算从源点到汇点的最大水流量（即“最大流”），即在不超过任何管道容量的前提下，能通过网络的最大流量。 解题步骤 基本概念建立 定义图 \( G = (V, E) \) ，其中 \( V \) 是节点集合，\( E \) 是边集合。 每条边 \( (u, v) \in E \) 有一个容量 \( c(u, v) \geq 0 \)。 源点记为 \( s \)，汇点记为 \( t \)。 目标：找到从 \( s \) 到 \( t \) 的最大流量值。 残量图与增广路径 残量图 ：对原图每条边 \( (u, v) \)，添加反向边 \( (v, u) \)，初始容量为 0。 当正向边有流量 \( f(u, v) \) 时，残量容量更新为： 正向边剩余容量：\( c(u, v) - f(u, v) \) 反向边容量：\( f(u, v) \)（表示可回退的流量） 增广路径 ：在残量图中找到一条从 \( s \) 到 \( t \) 的路径，路径上所有边残量容量均大于 0。 关键思想 ：通过不断寻找增广路径并增加流量，逐步逼近最大流。 算法流程 步骤1 ：初始化所有边流量为 0。 步骤2 ：在残量图中用任意路径搜索算法（如 BFS 或 DFS）找一条增广路径。 步骤3 ：若找到路径，计算路径上的最小残量容量（即“瓶颈容量”），将该值加到路径所有边的流量中，并更新残量图（减少正向边容量，增加反向边容量）。 步骤4 ：重复步骤2-3，直到无法找到增广路径为止。此时的总流量即为最大流。 实例演示 假设简单网络： 边及容量：\( s \to A: 3, \ s \to B: 2, \ A \to B: 1, \ A \to t: 2, \ B \to t: 3 \) 第1次增广 ：路径 \( s \to A \to t \)，瓶颈容量 2，更新流量。 第2次增广 ：路径 \( s \to B \to t \)，瓶颈容量 2，更新流量。 第3次增广 ：路径 \( s \to A \to B \to t \)，瓶颈容量 1，更新流量。 最终总流量为 \( 2 + 2 + 1 = 5 \)，无法再找到增广路径。 算法优化与注意点 Edmonds-Karp 算法 ：使用 BFS 找增广路径，保证时间复杂度为 \( O(V E^2) \)。 反向边的作用 ：允许算法撤销之前的流量分配，避免局部最优。 终止条件 ：当残量图中 \( s \) 和 \( t \) 不连通时，算法结束。 通过以上步骤，Ford-Fulkerson 方法能系统性地求解最大流问题，其核心在于残量图与增广路径的迭代优化。