EK算法详解：网络流中的增广路与最大流

EK算法是解决网络流问题中的一个重要方法，它针对的是求解有向图中从源点s到汇点t的最大流量问题。在这个背景下，网络流具有三个基本特性：流量不超过边的容量上限、流量的双向对称性和节点流量平衡。网络流问题的核心是找到最大流，而EK算法通过寻找增广路来逐步增大流值，直到达到极限。 1. **增广路**：增广路是指在残留网络中，一条从源点s出发，经过一系列边，最终到达汇点t的路径。这条路径上的每条边在原有流量限制下仍有剩余流量可以利用。增广路的存在表明还有提升流值的可能性。 2. **残留网络**：在进行增广操作后，残留网络是原始网络的一个子集，只包含那些未被完全利用的边。这些边的流量称为残量，表示它们还能承载的最大流量。当没有增广路时，表明所有边都被充分利用，无法再增加流量，此时网络已达到最大流状态。 3. **增广路定理**：这个定理指出，网络的最大流等于残留网络中不存在增广路时的最大流量。这意味着只要能找到一条增广路，就可以进一步增加流值，直到所有可能的增广路径都被尝试过。 EK算法的执行过程可以概括为以下步骤： - 初始化流值f为0。 - 使用宽度优先搜索（BFS）查找是否存在一条增广路。 - 如果找到增广路，沿着路径增加最小流量的边的流量，并重复此过程。 - 当找不到增广路时，算法停止，此时的流值即为最大流。 相比之下，Dinic算法是对EK算法的一种优化，它采用了分阶段的方式在层次图中增广。首先，计算初始流量和剩余图，然后构造层次图，通过深度优先搜索（DFS）在当前层次中寻找增广路。如果找不到增广路，就切换到下一个层次继续搜索，直到汇点加入层次图或无更多增广路径可寻。 在实际应用中，如题目示例所示，通过BFS分层次找出最短路径，再用DFS来寻找增广路。例如，在给定的图中，1号店到6号点的最大流为3，但如果(1,2)边的流量减小，可能会影响最大流的结果。 总结来说，EK算法和Dinic算法是求解网络流问题的有效工具，它们都依赖于对增广路和残留网络的理解，通过迭代更新流量和搜索策略，逐步逼近最大流。理解这些概念和算法的关键在于掌握它们的工作原理和适用场景，以及如何在实际问题中灵活运用。