搜索
BY-外向孤独患者-【那一天，人类终于回想起了曾一度被它们所支配的恐怖和被囚禁于鸟笼中的那份屈辱。】【人，只有在放弃战斗的时候才算输，只要坚持战斗，就还没输。】玛利亚之墙被攻破！！！犹豫的骚年眺望远方！！！由于城墙被攻破，有居民们要从S城内逃到最为安全的T城中，S到T之间恰巧是一个无环的有向图，其中有n个城市（包括S，T），m条城市与城市之间的单向直通路，每条路上都有限定的最大人流量。埃尔文团长想知道运送多少居民由S到T的速率。ST22222222大家总说纷纭莫衷一是。。还是爱尔敏聪明，说这样的问题需要用到网络流。(☄⊙ω⊙)☄可是网络流在一千多年后才被发明出来，大家都不知道网络流是什么。。于是爱尔敏决定给大家补一补网络流的知识。。。（￣ー￣）网络：一个连通的赋权有向图D=（V、E、C），其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。流：网络上的流就是由起点流向终点的可行流假设G(V,E)是一个有限的有向图，它的每条边(u,v)∈E都有一个非负值实数的容量c(u,v)。如果(u,v)不属于E，我们假设c(u,v)=0。我们区别两个顶点：一个源点s和一个汇点t。一道网络流是一个对于所有结点u和v都有以下特性的实数函数（f:V×V→R）容量限制:f(u,v)≤c(u,v)一条边的流不能超过它的容量。斜对称:f(u,v)=-f(v,u)由u到v的净流必须是由v到u的净流的相反。流守恒:除非u=s或u=t，否则Σ（w∈V）f(u,w)=0一结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。证明就略了。。【弧的流量】容量网络G中的每条弧上的实际流量称作弧的流量。【可行流】在容量网络中满足下列条件的网络流称为可行流。1、弧流量限制：流量要大于等于0且小于等于弧的容量。2、平衡条件：流量只能从源点流出经过容量网络在汇点会聚。在网络中不会凭空出现和消失。【伪流】满足限制条件但不满足平衡条件的网络流。也称为容量可行流。【最大流】在容量网络中，满足弧流量限制条件和平衡条件的最大可行流，称为网络最大流，简称最大流。【饱和弧与非饱和弧】在容量网络中的某一条弧当流量等于容量时，此弧为饱和弧，否则为非饱和弧。【零流弧和非零流弧】在容量网络中的某一条弧当流量等于零时，此弧为零流弧，否则为非零流弧。【链】在容量网络中，顶点序列（U1，U2……Un，V）为一条链，要求两个相连的点之间有一条弧。注意：链和有向图中有向路径不是相同概念，有向路径中有向边的方向是相同的，但链这里不要求这样。【正方向】设P为容量网络中源点到汇点的一条链，由源点到汇点的方向就为正方向。【前向弧与后向弧】方向与链的正方向相同的弧称为正向弧。反之称为后向弧。【增广路】在容量网络中P是从源点到汇点的一条链，如果：P的所有前向弧都为非饱和弧。则称P是一条增广路（增广链或可改进路）。沿着增广路改进可行流的操作称为增广。【残留容量】对于给定的容量网络中某条弧的容量为C，流量为F，残留容量就位C-F。【残留网络】以残留容量建成的容量网络。也称为剩余网络。根据网络流的特性和增广路的定义我们可以得到这样的性质：设增广路P，该路径最多额外流量为c(P)=min{c(u,v)|,u,v∈P}这样一来，设增广的定义流fP为c(P)u,v∈PfP(u,v)=-c(P)v,u∈P0其他给定网络G中的一个流为f,则f+fP依然为网络G的一个流。最大流定理（增广路定理）如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。接下来我们讲最大流算法。最大流算法大致分为两类：增广路算法和预流推进重标号算法这次对于网络流的最大流算法中重点介绍增广路算法，因为比较常见。在isap中我们也会接触到预留推进重标号算法。Ford-Fulkson方法（FF）：Ford-Fulkson的具体步骤1、初始化网络中所有边的容量，cu,v继承该边的容量，cv,u初始化为0，其中边v,u即为回退边。初始化最大流为0。2、在残留网络中找一条从源S到汇T的增广路p。如能找到，则转步骤3,；如不能找到，则转步骤5。3、在增广路p中找到所谓的“瓶颈”边，即路径中容量最小的边，记录下这个值X，并且累加到最大流中，转步骤4。4、将增广路中所有cu,v减去X，所有cv,u加上X，构成新的残留网络。转步骤2。5、得到网络的最大流，退出。EK（Edmond-Karp）算法（最短路算法）：用最最最最最最最最朴素的BFS来寻找增广路我们定义e(u)为节点u上的余流，实际上我们并不需要计算各个h(v)，只需将h(s)标为n，其余标为0，算法也能逐步计算出各个点的h。网络流中的节点(除s,t)仅需要满足流入量不小于流出量。其中流入量大于流出量的节点，我们称之为活动节点。预流推进算法就是不断地将活动结点，变为非活动结点，使得预流成为可行流。具体分为两个方法：在刚刚的维护距离标号的方法中，我们用到了“预流推进重标号算法”（PushRelabel）①压入操作，选出一个活动顶点u。并依次判断残余网络G中每条边(u,v)，若h(u)=h(v)+1，则顺着这里条边推流，流量变化量df(u,v)=min(e[u],cf(u,v))，同时更新相应的e(u)，e(v)；②重标记操作，选出一个活动结点。如果对于残余网络G中每条边(u,v)，都有h(v)大于或等于h(u)，则需要对u进行重新标号，h(u)=min{h(v)+1}；在具体实现中，我们可以选择以下方法：①一般预流推进算法，在残余网络中，以先进先出队列维护活跃点，时间复杂度为O(V*V*V)；②最高标号预流推进算法（HLPPHighestLabelPreflowPush），在残余网络图中，每次检查最高标号的活跃点，需要用到优先队列，时间复杂度为O(V*V*E^0.5)这是传说中最快的算法。③把预流推进算法与增广路算法结合，时间复杂度为O(V*E*E)；我们主要介绍方法3，方法1,2可以在“可参考の网络资源”的[5][6][7][8]学习。SAP（ShortestAugmentingPath）算法：如果能让每次寻找增广路的时间复杂度降低下来，那么就能够提高算法效率了，sap使用距离标号的最短增广路算法就是这样的。距离标号及其维护：（1）距离标号：就是某个点到汇点的最小的弧的数量（2）设点i的标号为D[i]，那么如果将满足D[i]=D[j]+1的弧称为允许弧，且增广时只走允许弧，那么就可以达到“怎么走都是最短路”的效果。（3）每个点的初始标号可以在一开始用一次从汇点沿所有的反向边BFS求出，实践中可以初始设全部点的距离标号为0（4）当找增广路过程中发现某点出发没有允许弧时，将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加一。sap另外几个疯狂的常数优化：（1）当前弧优化（用于邻接表）：初始时当前弧是第一条弧，查找可行弧是从当前弧开始查找，找到一条可行弧就把这条弧设为当前弧。改变距离标号时把当前弧设为第一条弧。当前弧的写法之所以正确就在于任何时候我们都能保证在邻接表中当前弧的前面肯定不存在允许弧。（2）dinic的借鉴：每次找到路径并增广完毕之后不要将路径中所有的顶点退栈，而是只将瓶颈边以及之后的边退栈（3）GAP（缺口）优化：当网络中距离标号出现断层时，残余网络中无法得到新流。ISAP（ImprovedSAP）算法：推荐算法之一当SAP优化到这个程度上的时候（准确的说ISAP集合了增广路算法和预流推进重标号算法的优势），它已经升级了！！！有了刚刚优化的基础，所以直接丢代码了嘎嘎。。事实上，代码可以更短。我们把ISAP的实现方式改为DFS，就像等会要介绍的DINIC一样Dinic算法（阻塞流算法BlockingFlowAlgorithm）：推荐算法之一层次图(分层网络):就是把原图中的点按照到到源的距离分“层”，只保留相邻层(或同层)之间的边的图。在层次图中求得自己的层数A[i]就可以按照A[i]=A[j]-1这样的有用边寻找增广路。多路增广：用DFS从源点开始前一层至后一层寻找增广路。实现步骤：1、初始化流量2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束3、在层次图内用一次dfs过程增广4、转步骤2一般情况下ISAP比DINIC快（偶不确定。。），可以参考“可参考の网络资源”的[9]现在我们就可以解决章首的那个问题了。请思考：如果在章首的那个问题中，每个城市也有一定的饱和度，那么这样一来问题应该如何解决呢？(⊙o⊙)？1.://comzyh.com/blog/archives/568/3.://://://blog.csdn.net/d891320478/article/details/84248207.://blog.sina.com.cn/s/blog_60707c0f01010oqt.html9.大家可以试着用不同方法做“草地排水”！——【什么都无法舍弃的人，什么都无法改变。】人类对巨人的研究出现新进展！！！巨人是否还能笑到最后！！！人类发现巨人控制吃人的神经是有一些神经元和一些神经通道组成的，每个神经通道两端各有一个神经元，且这个通道是单向的。吃人信号从脑部神经元S发出到控制吃人的神经元T，S、T之间是一个有向无环图。人类想把某些神经通道切断达到S的信号无法传到T（由于神经元太小不容易砍掉，所以考虑神经元），每个神经通道由于位置的不同也有砍断所需的力量。人类想知道如何花最小的力气而使S的信号传不到T。ST22222222这样的问题就是在刁难我们嘛。。^(*￣(oo)￣)^艾伦隐约觉得这个问题和爱尔明之前说的网络流很相似。。(ง•̀_•́)ง可是这个跟网络流明明没有一点关系嘛(；′⌒`)于是艾伦就和大家辩驳起来。。∑q|ﾟДﾟ|p1.割的概述：将拥有源点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-TCUT：所有从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流的值，这个