浅谈基于，分层思想，网络，流算法.pptx

浅谈基于分层思想的网络流算法最短路径增值(MPLA)DinicMPM2007冬令营讲座什么是剩余图？剩余图G’=(V,E’)流量网络G=(V,E)中，对于任意一条边(a,b)，若flow(a,b)capacity(a,b) or flow(b,a)0则(a,b)∈ E’可以沿着a---b方向增广2007冬令营讲座有向图Capacity=5Capacity=2Capacity=6Flow=2Flow=2Flow=2剩余图34222剩余图的权值代表能沿边增广的大小剩余图中，每条边都可以沿其方向增广剩余图中，从源点到汇点的每一条路径都对应一条增广路2007冬令营讲座一、最短路径增值(MPLA)顶点u的层次：level(u)=在剩余图中从源点到u所经过的最少边数层次图：对于剩余图中的任意一条边(a,b),当且仅当level(a)+1=level(b)时,(a,b)是层次图中的边Level=1Level=2Level=3Level=0源点Level=32007冬令营讲座一、最短路径增值(MPLA)算法步骤1、初始化流量，计算出剩余图2、一次bfs对顶点标号，计算出层次图，如果汇点不在层次图内，那么算法结束3、不断在层次图中寻找增广路进行增广，并修改剩余图多次bfs4、转步骤 22007冬令营讲座定理：对于有n个点的流量网络，在最短路径增值算法中，最多建立n次层次图。 证明这个定理有助于进行算法复杂度分析 在建立完层次图以后，假设从源点到汇点的最短路径长度为k，我们将层次图中所有的点分到k+1个集合中，第i个集合为{顶点u|level(u)=i-1}2007冬令营讲座在剩余图中，存在着2类边 源点第一类：从第i个集合中的顶点连到第i+1(1=i=k)个集合中的顶点{level=1的顶点}{level=2的顶点}第二类：从第i(1=i=k+1)个集合中的顶点连到第j(1=j=i)个集合中的顶点..{level=3的顶点}...在层次图中，只存在第一类边，这是由层次图的性质决定的。不存在从level=i的顶点连到level=i+j(j=2)的边{level=k-1的顶点}汇点2007冬令营讲座一次增广的效果：与增广路的方向相反删除一条或多条边可能增加一条或多条回边剩余图源点汇点846244426增广4个单位的流量2007冬令营讲座层次图中找完增广路径以后，剩余图中的最短路径：源点{level=1的顶点}从源点开始，往下一步一步走，走到某个集合后沿着第二类边向上退至某个集合，再继续一步一步向下走，到某个集合又向上退…………直到走到汇点。 每一条增广路径都是从源点一步一步向下走到汇点。{level=2的顶点}.{level=3的顶点}..必然会经过第二类边经过的第一类边的数量=k {level=k-1的顶点}汇点2007冬令营讲座一、最短路径增值(MPLA)层次图中增广路径长度序列严格递增1=路径长度=n-1最多建n次层次图2007冬令营讲座一、最短路径增值(MPLA)复杂度分析最多有n层每层做一次bfs标号O(m)建层次图：O(n*m)2007冬令营讲座一、最短路径增值(MPLA)复杂度分析每增广一次至少删除一条边最多有n层找增广路：最多找m次增广路找增广路bfs O(m)O(n*m*m)2007冬令营讲座一、最短路径增值(MPLA)复杂度O(n*m2)程序简短对于中小规模数据速度快2007冬令营讲座二、Dinic算法步骤1、初始化流量，计算出剩余图2、一次bfs对顶点标号，计算出层次图，如果汇点不在层次图内，那么算法结束3、一次dfs过程找增广4、转步骤 22007冬令营讲座二、Dinice栈dcfbfa55汇源e1055010505abcd后退到原路径中从源点能够到达的最远点2007冬令营讲座p?s;While 源点没有被删除 u?p.top; if ut if outdegree(u)0 设(u,v)为层次图中的一条边; p?p,v; else 从p和层次图中删除点u, 以及和u连接的所有边; else 增广p（删除了p中的饱和边）; 令p.top为p中从s可到达的最后顶点;end while 2007冬令营讲座二、Dinic复杂度分析O(n*m)建层次图： +dfs找增广路：O(n*n*m)2007冬令营讲座层次图中最多找m次增广路每次在dfs中最多前进n次，花费O(n)每次修改流量花费O(n)一次Dfs复杂度为O(m*n)2007冬令营讲座二、Dinic复杂度O(n2*m)程序简短对于较大规模的数据实际速度很快2007冬令营讲座三、Dinic 的应用Noi2006 最大获利： 一共有N 个通讯信号中转站，建立第i个通讯中转站需要的成本为Pi(1≤i≤N)。 另有M 个用户群，第i 个用户会使用中转站Ai 和中转站Bi 进