网络流入门：最大流算法详解与建模技巧

网络流从入门到深入理解是一门复杂的主题，特别是对于那些想要掌握该领域的专业人士而言。本文档《网络流从入门到入土》由MolotovM整理，旨在提供一个全面的教程，适合初学者和进阶者学习。首先，让我们回顾一下前置图论知识： 1. **网络流定义**：网络流是指在一个有向图中，源点S只有一个，汇点T也唯一，每条边都有一个非负容量，表示该边能承载的最大流量。网络图中，每条边同时有两个量：容量c[u][v]和流量f[u][v]，流量不能超过容量。 2. **可行性与性质**：合法的网络流被称为可行流，它满足流入节点的流量等于流出节点的流量（除S和T）。如果一条边的流量达到其容量，该边的残量为零，表示无法再通过此路径传输更多流量。 3. **残量网络**：当网络中的流量达到最大时，可以通过残量网络分析，它是原网络中每条边剩余容量构成的网络。残量网络用于检测是否存在增广路。 接下来是关键部分：**最大流算法**，特别是Ford-Fulkerson算法（FF算法）的介绍： - **增广路与最大流**：算法的核心是寻找增广路，即一条从源点S到汇点T且未达到最大流量的路径。每次找到增广路后，沿路径增加流量，直至无增广路可寻，此时的流量即为最大流。 - **反向边的应用**：在FF算法中，为了克服某些路径可能被占用的情况，引入了反向边。例如，当无法通过2-3这条正向边增加流量时，会创建一条从3到2的反向边，以“退”回已使用的流量，并尝试其他路径（如2-4）。 - **深度优先搜索（DFS）的应用**：DFS在找寻增广路时发挥重要作用，它是一种递归的遍历策略，通过探索所有可能的路径，确保最大流的计算效率。 这份文档涵盖了网络流的基本概念，包括最大流最小割定理的理论基础，以及最大流算法中的关键策略，特别是福特-弗洛克森算法的执行细节。对于想要学习和实践网络流算法的人来说，这是一份不可或缺的参考资料。