算法合集之《浅谈基于分层思想的网络流算法》

《算法合集之《浅谈基于分层思想的网络流算法》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈基于分层思想的网络流算法上海市延安中学王欣上Email:wxsxg@hotmail.com最短路径增值(MPLA)DinicMPM2007冬令营讲座剩余图G’=(V,E’)流量网络G=(V,E)中，对于任意一条边(a,b)，若flow(a,b)0则(a,b)∈E’什么是剩余图？可以沿着a--->b方向增广2007冬令营讲座剩余图中，从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩

2、余图剩余图中，每条边都可以沿其方向增广剩余图的权值代表能沿边增广的大小2007冬令营讲座顶点u的层次：level(u)=在剩余图中从源点到u所经过的最少边数源点Level=0Level=2Level=3Level=1Level=3层次图：对于剩余图中的任意一条边(a,b),当且仅当level(a)+1=level(b)时,(a,b)是层次图中的边一、最短路径增值(MPLA)2007冬令营讲座一、最短路径增值(MPLA)算法步骤4、转步骤23、不断在层次图中寻找增广路进行增广，并修改剩余图2、一次bfs对顶点标号，计算出层次图，如果汇点不在层

3、次图内，那么算法结束1、初始化流量，计算出剩余图多次bfs2007冬令营讲座定理：对于有n个点的流量网络，在最短路径增值算法中，最多建立n次层次图。在建立完层次图以后，假设从源点到汇点的最短路径长度为k，我们将层次图中所有的点分到k+1个集合中，第i个集合为{顶点u

4、level(u)=i-1}证明这个定理有助于进行算法复杂度分析2007冬令营讲座{level=1的顶点}源点{level=2的顶点}{level=3的顶点}{level=k-1的顶点}汇点.....不存在从level=i的顶点连到level=i+j(j>=2)的边在剩余图中，存

5、在着2类边第一类：从第i个集合中的顶点连到第i+1(1<=i<=k)个集合中的顶点第二类：从第i(1<=i<=k+1)个集合中的顶点连到第j(1<=j<=i)个集合中的顶点在层次图中，只存在第一类边，这是由层次图的性质决定的。2007冬令营讲座删除一条或多条边648224446可能增加一条或多条回边一次增广的效果：与增广路的方向相反源点汇点增广4个单位的流量剩余图2007冬令营讲座{level=1的顶点}源点{level=2的顶点}{level=3的顶点}{level=k-1的顶点}汇点...每一条增广路径都是从源点一步一步向下走到汇点。从

6、源点开始，往下一步一步走，走到某个集合后沿着第二类边向上退至某个集合，再继续一步一步向下走，到某个集合又向上退…………直到走到汇点。必然会经过第二类边经过的第一类边的数量>=k层次图中找完增广路径以后，剩余图中的最短路径：2007冬令营讲座层次图中增广路径长度序列严格递增最多建n次层次图一、最短路径增值(MPLA)1<=路径长度<=n-12007冬令营讲座一、最短路径增值(MPLA)建层次图：复杂度分析最多有n层O(n*m)每层做一次bfs标号O(m)2007冬令营讲座一、最短路径增值(MPLA)复杂度分析找增广路：最多有n层最多找m次增广

7、路找增广路bfsO(m)O(n*m*m)每增广一次至少删除一条边2007冬令营讲座一、最短路径增值(MPLA)对于中小规模数据速度快复杂度O(n*m2)程序简短2007冬令营讲座二、Dinic4、转步骤2算法步骤1、初始化流量，计算出剩余图3、一次dfs过程找增广2、一次bfs对顶点标号，计算出层次图，如果汇点不在层次图内，那么算法结束2007冬令营讲座二、Dinicabdcef10551055源汇栈abcde5500后退到原路径中从源点能够到达的最远点f2007冬令营讲座ps;While源点没有被删除up.top;ifu<>tifou

8、tdegree(u)>0设(u,v)为层次图中的一条边;pp,v;else从p和层次图中删除点u,以及和u连接的所有边;else增广p（删除了p中的饱和边）;令p.top为p中从s可到达的最后顶点;endwhile2007冬令营讲座二、Dinic建层次图：+dfs找增广路：O(n*m)O(n*n*m)复杂度分析2007冬令营讲座层次图中最多找m次增广路每次在dfs中最多前进n次，花费O(n)每次修改流量花费O(n)一次Dfs复杂度为O(m*n)2007冬令营讲座二、Dinic复杂度O(n2*m)程序简短对于较大规模的数据实际速度很快200

9、7冬令营讲座三、Dinic的应用Noi2006最大获利：一共有N个通讯信号中转站，建立第i个通讯中转站需要的成本为Pi(1≤i≤N)。另有M个用户群，第i个用户会使用中转站Ai和