有界容量下网络的s-t最大/最小流算法详解

有容量下界网络的s-t最大/最小流问题是网络流理论中的一个重要分支，它考虑了网络中的流量不仅受到容量上限的限制，还可能存在下限。在这个问题中，我们面对的是一个简单的有向图，其中包含一个源点s和一个汇点t，以及每条弧（u, v）都有一个正的容量C(u, v)。网络的流量必须满足以下两个关键条件： 1. 流量容量限制：每条弧的流量不能超过其容量上限，即0 <= f(u, v) <= C(u, v)。 2. 流量平衡条件：除了s和t之外，所有其他节点的入流量等于出流量。 要找到s到t的最大流，首先需要找到一个可行流，即满足以上条件的流。可以使用传统的s-t增广路算法，从s出发，通过连续找到并利用可增广路径（即既存在未充分利用的前向弧又存在可以增加流量的后向弧的路径）来逐步增加流量，直到无法再添加为止。这个过程可以保证找到的最大流是网络上的最大值。 而最小流可以通过以下方法求得：将t视为新的源点，s视为新的汇点，此时的t-s最大流就是原来的s-t最小流。注意，由于容量下界的存在，原图中每条弧的反向弧容量应设置为其下界。 在求解过程中，残留网络的概念至关重要。通过将前向弧的容量调整为剩余容量（C(u, v) - f(u, v)），后向弧的容量调整为可退流量（f(v, u)），并且删除流量为零的弧，可以简化网络结构，更容易发现可增广路径。基于最大流定理，如果在残留网络上无法找到可增广路径，那么当前的流量就是最大流；反之，若能找到可增广路径，则继续增加流量，直至无更多增广路径为止。 寻找可增广路径的方法有多种，包括深度优先搜索（DFS）、广度优先搜索（BFS）以及标号搜索等。这些算法的核心都是在确保流量限制的前提下，有效地遍历网络结构，直到达到最大流或者确定不存在更大的流量增量。 总结起来，有容量下界网络的s-t最大/最小流问题涉及网络流的理论基础、流量限制、流量平衡、可增广路径的定义和寻找方法，以及如何通过残余网络来简化问题求解。掌握这些概念和算法是理解和解决这类问题的关键。