最小费用最大流剖析.pptVIP

最小费用最大流;概念 ;如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问 ：若从起点v1将物资运送到终点v6去 ，应选择那条路线才能使总运输距离最短? 这样一类问题称为最短路问题 。 如果把上图看作一个输油管道网 ， v1 表示发送点，v6表示接收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。;网络流问题 ; 如果 f 是可行流,则对收、发点vt、vs有 ∑fsi =∑fjt =Wf , 即从vs点发出的物质总量 = vt点输入的量.Wf 称为网络流 f 的总流量. ;网络流算法;可改进路(可增广路）　　给定一个可行流f。若fij = cij，称vi, vj为饱和弧；否则称vi, vj为非饱和弧。若fij = 0，称vi, vj为零流弧；否则称vi, vj为非零流弧。　　定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。 ;　　譬如在图中，P = (S, V1, V2, V3, V4, T)，那么　P+ = {S, V1, V1, V2, V2, V3, V4, T}　P- = {V4, V3}　　给定一个可行流f，P是从S到T的一条道路，如果满足： 　 那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。 ; 所谓最大流问题就是在容量网络中,寻找流量最大的可行流.譬如对上图而言，它的最大流如下： ;　　在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则”。　　对可改进路P上的弧vi, vj，分为两种情况讨论：　　第一种情况：vi, vj∈P+，可以令fij增加一个常数delta。必须满足 fij + delta ≤ cij，即delta ≤ cij – fij。　　第二种情况：vi, vj∈P-，可以令fij减少一个常数delta。必须满??? fij - delta ≥ 0，即delta ≤ fij　　根据以上分析可以得出delta的计算公式： 因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，∴delta0。　　容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量 守恒”（即输入量等于输出量），又可以使得总的流量有所增加 （因为delta 0）。　　因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可 以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在 的问题是：倘若在f中找不到可改进路，是不是f就一定是最大流呢？;最大流算法 ;最大流算法SAP ;实例;实例;实例;实例; 再回到求网络最大流的算法中来。算法的关键步骤是step 2，即：判断是否存在可改进路，若存在又如何求。 可以考虑用广度优先有哪些信誉好的足球投注网站。设置标志数组，记录顶点是不是被访问过；使用队列来存储已经访问过的顶点；另用一个一维数组，记录每个顶点是由哪个顶点扩展而来（即记录父亲节点）。 首先S入队列。然后每次取队首顶点v，分析所有与v相邻的未访问顶点u： 1）存在弧v, u（正向弧），且u未访问。若fvuCvu（非饱和弧），那么u入队列，给u打上“已访问”的标志，记u的父亲节点为v。 2）存在弧u, v（反向弧），且u未访问。若fuv 0（非零流弧），那么u入队列，给u打上“已访问”的标志，记u的父亲节点为-v。（以示和正向弧的区别）。 扩展完成后，若T还没有被访问就必然不存在可改进路；否则就从T出发，根据记录好的每个顶点的父亲节点信息，顺藤摸瓜，找出可改进路（同时还可以计算出delta）。 这只是算法的初步勾勒，具体细节的优化余地极大，留给读者思考。 注：有些书上是介绍的用“标号法”求可改进路。“标号法”实质上就是广搜，只是细节的实现上略有偏差。; 实际问题中,一个网络会出现下面两种情况： ⑴ 发点和收点都不止一个. 解决的方法是再虚设一个发点vs和一个收点vt ,发点vs到所有原发点边的容量都设为无穷大, 所有原收点到收点vt 边的容量都设为无穷大. ⑵ 网络中除了边有容量外,点也有容量. 解决的方法是将所有有