增广算法

A. 网络流理论求最大流有两种常用的算法

网络流理论中求解最大流问题，有两类常用的算法，其中之一是augment path，即“增广路”算法。该算法的基本思路如下：

首先，我们从原始网络G出发，构建辅助图G'，其顶点V(G')与G相同，初始边的容量E(G')与E(G)一致。每次操作中，从源点Source开始，寻找一条从Source到Sink的路径。沿着这条路径，将每条边的容量减去路径上容量最小值，然后对路径上每条边，在其反方向增加或扩展容量，即刚才减去的容量。这个过程会一直持续，直到无法找到新的路径为止。此时，辅助图G'上的正向流量即为最大流。

虽然直观上可能会担心算法会陷入无限循环，实际上，由于每次操作都增加了从Source到Sink的流量，且假设容量和流都是整数，这个过程会自然终止。寻找路径时，可以选用DFS或BFS搜索算法，BFS通常比DFS更快，但代码量也会相应增加。

然而，augment path方法的一个局限是，在极端情况下，每次只能将流扩大1，这在性能上造成较大影响。为解决这个问题，另一种更复杂的算法就是预推进（push label）算法。预推进算法能够更有效地处理大规模数据，提高求解最大流的效率，虽然它可能需要更复杂的实现，但其性能优势显而易见。

所谓网络或容量网络指的是一个连通的赋权有向图D＝（V、E、C），其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。