网络流初步课件.ppt

连续最短路算法基本思路： 把弧i,j的单位费用w[i,j]看作弧i,j的路径长度，每次找从源点s到汇点t费用最小的可增广路径进行增广直至无法增广。 若用dijkstra寻找费用最小的增广路，但是由于负边权的出现我们暂不考虑。 （实际上是可以实现的，而且速度比下面介绍的方法略快，参见可参考的网络资料[3]） 我们可以考虑综合性价比较高的SPFA来寻找增广路，这样最小费用最大流就可以较简单的实现了。 这里的2*N+1是对于某某题而言的，一般就n好了 人类发现巨人控制吃人的神经是有一些神经元和一些神经通道组成的，每个神经通道两端各有一个神经元，且这个通道是单向的。吃人信号从脑部神经元S发出到控制吃人的神经元T，S、T之间是一个有向无环图。人类想把某些神经通道切断达到S的信号无法传到T（由于神经元太小不容易砍掉，所以考虑神经元），每个神经通道由于位置的不同也有砍断所需的力量。人类想知道如何花最小的力气而使S的信号传不到T。 S T 2 2 2 2 2 2 2 2 这样的问题就是在刁难我们嘛。。^(*￣(oo)￣)^ 艾伦隐约觉得这个问题和爱尔明之前说的网络流很相似。。(? ??_??)? 可是这个跟网络流明明没有一点关系嘛(；′⌒`) 于是艾伦就和大家辩驳起来。。∑q|?Д?|p 1.割的概述：将拥有源点s和汇点t的结点集合V分成两个子集S和T，当且仅当s属于S且t属于T时，称这种分割为割（cut）。如下图中左图为割，右图则不是。 2.s-t的容量：cap([S, T]) 指的是所有从S到T的边界的容量和，具体公式如下： 下面是个例子，注意此外只计算从S到T的，不计算T到S的 ： 最小割就是所有可能的s-t割中容量最小的s-t割。 3.交叉流S-T CUT：所有从S中的结点到T中结点流之和 - 所有从T中的结点到S中的结点的流之和。 下图是个例子，此处计算从S到T和T到S。 注意S-T交叉流和下面的流区分开 4.根据流守恒的性质我们可以推广这样一个性质： 所有从源点出发的边的流量之和 - 所有到源点的边的流量 = 流量的值 所有从汇点出发的边的流量之和 - 所有到汇点的边的流量 = 负的流量值 所有非源点和非汇点出的边的流量之和 - 到这些点的边的流量之和 = 0 以下是流量的一个例子，源点出发的 2+3，到源点的为0，则流量为5,，类似推理其他点 这里最大流就是可能的流函数中最大的 我在一开始的时候提出了网络流和最小割是等价的。做了那么多铺垫之后现在给出证明： 性质一： 对于任意的s-t割和流，s-t割的容量是s-t割交叉流量的上界（即最大值），推理过程很简单。 性质二： 对于任意的s-t割，割的交叉流量的值等于s-t流的值，这个推理稍微麻烦一点儿，主要思想是把前一项的终点分为S和T，后一项的起点分为S和T，再把前一项加和合并。 这样，对于任意的s-t割和流，s-t割的容量是流的值的上界。这是由性质一和性质二推理出来的。 这样我们得到一个重要定理： 最小割最大流定理：最小割集的流量之和等于网络中的最大流 以上证明皆可在有用的网络资源[1]中找到 “好吧，虽然已经知道要花多少力气了，可是还是不知道要怎么割呀。” 艾伦说他还没有说完，大家稍安勿躁。。(/▽＼) 大家又开始怀疑艾伦的能力 于是艾伦就和大家辩驳起来。。(╰_╯)# 1.割集：割掉的所有边构成一个割集 2.最小割集：某割满足最小割时，割掉的所有边构成一个割集 如何求最小割集呢？有没有什么好想法？ Floodfil的解决方案： 1.在做完最大流的残余网络中以S开始做一遍Floodfill 2.枚举每条边若边的一端被访问过，另一端没有则说明该边在最小割集中 这个方法貌似很正确。。 可是如果割集不唯一就很麻烦了： S T 2 1 1 1 2 2 2 2 在最小割有多组解的情况下，我们把边数最小的割重新定义为最小割。 这就涉及到网络流多关键字的问题。 我们可以用加权来解决这个问题。 重新设定每条边的容量,将C?C*(M+1)+1 S T 19 10 10 10 19 19 19 19 这样边数最少的最小割就可以解决了。 1的个数不会影响到前面C的选择（不影响网络流），而在C最小的情况下，同时1也会变成最小。 也就是说Cmin’=cmin*(m+1)+minedges cmin=cmin’ div (m+1) Minedges=cmin’ mod (m+1) 可是就算是边数最少，又有可能出现多种情况啊？就像下面这样： 把边标号，我们把最小割集再定义为边数最小的最小字典序的割集 那么最小字典序的割集可不可以也用C+（N+1）+1来实现呢？ S T 2 1 1 1 2 2 2 2 NO！这样只能求出字典序和最小的割集。。 为了解决这个问题，