网络流总结-网络的最大流.doc

序言：没有哪种学习是枯燥的，除非你一无所获；没有哪种知识是无用的，除非你只掌握皮毛。青春很激昂，也不可逆转。谨以此文，纪念那段为网络流奋斗的日子，同时也是对网络流知识的积累，概括与总结。 目录： 第一部分：网络的最大流 第二部分：构图技巧 第三部分：最大流算法总结 第四部分：费用流 第五部分：有上下界的网络流 第六部分：网络流题目列表 符号说明： N：点数 E：边数 S：源点 T: 汇点 f: 流 c：容量 u,v,i,j：节点的标号 INF：正无穷大 -INF：负无穷大 名词说明：弧：即边 Spfa: Shortest Path Faster Algorithm，一种求单源最短路的算法。 时间复杂度：算法的理论时间上界 时间效率：实际中算法运行的平均时间效率 引用说明：文中参考了许多来源于网络的资料，也有原文全段引用的部分。在这些资料被n+1次转载后，我已无法获知所有原作者的信息。在此，对所有前辈们表示真诚的歉意和诚挚的敬意。特别感谢：Matrix67，ZY，HH大神们的犀利文字。 作者：Snow_storm 正文： 第一部分：网络的最大流 什么是网络？考虑一个简单的例子： 现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如图 1-1： 每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？ 图 1-1 网络可以被想象成一些运输的公路。括号内右边的数字表示公路的运载量,左边的数字表示这条公路的当前运载量。 结合图1-1，简单思考后，可知S到T的最大运载量是5。类似于图1-1的这种关系图形就被称为网络，而求网络中的最大运载量问题，就是网络流中的最基本问题：最大流。 接来下，我们对一些名词作必要的了解： 第一个需要解释的名词是路径： 什么是路径？就是从一个点到另一个的通路，且每个顶点至多被经过一次；例如在图1-1中：S-a-c-T就是一条路径；S-b-d-T是另一条路径。 接下来说说什么是流（flow）：?? 在一个有向图中，把只有出去的边而没有进来的边的节点叫做源(source)，把只有进来的边而没有出去的边的节点叫做汇(sink)，其它的节点进来的边和出去的边应该是平衡的。?? 边上可以加权值，假设对于一个交通图来说，可以认为边上的权重为一条道路上的最大流量。那么对于图中任意两个节点来说，他们之间可以存在多条路径，每条路径上可以负载的最大流量应该是这条路径上权重最小的那条边所能承载的流量（联想一下“瓶颈”这个词，或者木桶理论）。那么所有的路径上所负载流量之和也就是这两个节点之间所能通过的最大流了（max flow）。 然后是符号的声明和定义： V表示整个图中的所有结点的集合. E表示整个图中所有边的集合. G = (V,E) ,表示整个图. s表示网络的源点,t表示网络的汇点. 对于每条边(u,v),有一个容量c(u,v) (c(u,v)=0) 如果c(u,v)=0，则表示(u,v)不存在于网络中。 如果原网络中不存在边(u,v)，则令c(u,v)=0 对于每条边(u,v),有一个流量f(u,v). 关于网络流的三个性质与可行流: 1、容量限制: f[u,v]=c[u,v] 2、反对称性：f[u,v] = - f[v,u] 3、流量平衡: 对于不是源点也不是汇点的任意结点，流入该结点的流量和等于流出该结点的流量和。 结合反对称性,流量平衡也可以写成: 只要满足这三个性质,就是一个合法的网络流,也称为可行流。 第一个性质很好理解，就是说某条公路的运载量不能超过规定的上限。 第二个性质，也就是说从点U流向点V的流量在数值上等同于点V流向点U的流量，但方向相反。 第三个性质表明，每个中转站是没有存储货物的功能，或者说在中转站存储货物是没有意义的，因为最终的目标是将货物从S运送到T。 现在，定义一个网络的流量（记为|f|）= 而最大流问题，就是求在满足网络流性质的情况下，|f|的最大值。 很显然的一个性质：当网络中不存在可行流时，汇点收集到的流量总和可能是最大流；当网络达到最大流时，一定不存在可行路。这就给解决最大流问题的近似解提供了一种最基本的思路：不断寻找流量大于零的可行流，然后修改网络中对应边的当前容量，直到无法找到流量大于零的可行流。对于流量大于零的可行流，不妨称之为：可行路。 注意到