Ford-Fulkerson方法求最大流问题 题目描述 假设有一个有向图，其中每条边都有一个非负的容量（capacity），表示该边能承载的最大流量。图中有一个特定的源点（source）和一个特定的汇点（sink）。最大流问题的目标是找到从源点到汇点的最大可能流量，使得每条边上的流量不超过其容量，并且除了源点和汇点外，所有顶点的流入流量等于流出流量（流量守恒）。 解题过程 Ford-Fulkerson方法是一种用于求解最大流问题的经典算法。其核心思想是不断在残留图中寻找增广路径（augmenting path），并沿该路径增加流量，直到无法找到增广路径为止。以下是详细步骤： 初始化流量 将图中所有边的初始流量设为0。 构建残留图（residual graph） 残留图与原图有相同的顶点集。 对于原图中的每条边 \( (u, v) \)，容量为 \( c(u, v) \)，当前流量为 \( f(u, v) \)： 在残留图中添加一条正向边 \( (u, v) \)，其残留容量（residual capacity）为 \( c(u, v) - f(u, v) \)（表示还能增加多少流量）。 同时添加一条反向边 \( (v, u) \)，其残留容量为 \( f(u, v) \)（表示可以撤销的流量，即回退流量的能力）。 寻找增广路径 在残留图中，从源点 \( s \) 到汇点 \( t \) 寻找一条路径，使得路径上的每条边的残留容量均大于0。路径可以使用DFS或BFS（后者称为Edmonds-Karp算法）寻找。 更新流量 设找到的增广路径上的最小残留容量为 \( \Delta \)（即路径上的瓶颈容量）。 对于路径上的每条正向边（与原图方向一致），将流量增加 \( \Delta \)。 对于路径上的每条反向边（与原图方向相反），将流量减少 \( \Delta \)（相当于回退流量）。 重复过程 重复步骤2-4，直到残留图中无法找到从源点到汇点的增广路径为止。此时，当前流量即为最大流。 示例说明 假设有一个简单图：源点 \( s \)，汇点 \( t \)，中间顶点 \( a \) 和 \( b \)。边及其容量为： \( s \to a \): 容量 10 \( s \to b \): 容量 10 \( a \to b \): 容量 5 \( a \to t \): 容量 15 \( b \to t \): 容量 10 初始化 ：所有流量为0。 第一次增广路径 ：找到路径 \( s \to a \to t \)，瓶颈容量为 10。更新后，边 \( s \to a \) 和 \( a \to t \) 的流量变为 10。 第二次增广路径 ：找到路径 \( s \to b \to t \)，瓶颈容量为 10。更新后，边 \( s \to b \) 和 \( b \to t \) 的流量变为 10。 第三次增广路径 ：在残留图中，路径 \( s \to a \to b \to t \) 的瓶颈容量为 5（因为 \( a \to b \) 的容量为 5）。更新后： \( s \to a \) 流量变为 15， \( a \to b \) 流量变为 5， \( b \to t \) 流量变为 15。 终止 ：残留图中无法再找到增广路径。最大流为 20（从 \( s \) 出发的流量总和）。 关键点 算法正确性依赖于最大流最小割定理（max-flow min-cut theorem）：最大流的值等于最小割的容量。 使用BFS寻找增广路径（Edmonds-Karp算法）可以保证时间复杂度为 \( O(V E^2) \)，避免DFS在某些情况下的低效问题。 反向边的引入确保了流量调整的灵活性，避免陷入局部最优。