北京大学ACM暑期课网络流算法详解

"北京大学ACM暑期课讲义-网络流" 这篇讲义主要涵盖了网络流算法的概念和福特-富克森（Ford-Fulkerson）算法的应用。网络流问题是在一个有向图中，通过源点s向汇点t传输流量的问题，其中每条边都有一个流量上限。关键在于满足流量守恒原则：源点流出的流量等于汇点流入的流量，而图中其他所有节点的流入流量等于流出流量。 福特-富克森算法是求解最大流的一种方法。它的基本思想是采用深度优先搜索（DFS）从源点s到汇点t寻找一条可行路径，并尽可能将这条路径的流量最大化。每次DFS找到的流量路径中，容量最小的边决定了这次增广的流量。然后更新所有路径上的边，减少它们的容量，以便于在后续的DFS中寻找新的增广路径。这个过程一直持续到找不到从源点到汇点的可行路径为止。 然而，原始的福特-富克森算法可能会遇到一个问题，即在某些情况下，由于过早地认为某些边的流量达到上限，可能导致未能发现更大的流量路径。为了解决这个问题，算法会添加反向边。反向边的容量等于上一次DFS中该边消耗的流量，这样就可以在新的网络结构中重新搜索可能的路径，避免“不合理”流量的出现。通过反复添加反向边和进行DFS，可以找到并合并多条路径，从而增加总的流量。 在讲义中，通过实例展示了如何应用这一算法。初始时，可能存在一条流量为100的路径s-a-b-t，但通过添加反向边和再次DFS，可以找到另一条流量也为100的路径，使得总流量达到200。当无法在当前的残余网络中找到更多的增广路径时，表明已经找到了最大流。 残余网络是网络流算法中的一个重要概念，它是在原网络基础上构建的，反映了当前还能传输多少额外流量的网络状态。在残余网络中，边的流量可以是负数，表示可以从目标节点流向源节点，这对应于原来的边的剩余容量。如果在残余网络中找不到从源点到汇点的路径，那么当前的最大流已经找到。 这篇讲义详细介绍了网络流问题的基本概念、福特-富克森算法的工作原理以及如何通过反向边和残余网络来优化搜索过程，是理解并解决最大流问题的一个很好的学习资料。