国家集训队2007论文集9.王欣上《浅谈基于分

浅谈基于分层思想的网络流算法上海市延安中学王欣上Email:[e-mail]2007冬令营讲座最短路径增值(MPLA)DinicMPM2007冬令营讲座剩余图G’=(V,E’)流量网络G=(V,E)中，对于任意一条边(a,b)，若flow(a,b)capacity(a,b)orflow(b,a)0则(a,b)∈E’什么是剩余图？可以沿着a---b方向增广2007冬令营讲座剩余图中，从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩余图剩余图中，每条边都可以沿其方向增广剩余图的权值代表能沿边增广的大小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对顶点标号，计算出层次图，如果汇点不在层次图内，那么算法结束1、初始化流量，计算出剩余图多次bfs2007冬令营讲座定理：对于有n个点的流量网络，在最短路径增值算法中，最多建立n次层次图。在建立完层次图以后，假设从源点到汇点的最短路径长度为k，我们将层次图中所有的点分到k+1个集合中，第i个集合为{顶点u|level(u)=i-1}证明这个定理有助于进行算法复杂度分析2007冬令营讲座{level=1的顶点}源点{level=2的顶点}{level=3的顶点}{level=k-1的顶点}汇点.....不存在从level=i的顶点连到level=i+j(j=2)的边在剩余图中，存在着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的顶点}汇点...每一条增广路径都是从源点一步一步向下走到汇点。从源点开始，往下一步一步走，走到某个集合后沿着第二类边向上退至某个集合，再继续一步一步向下走，到某个集合又向上退…………直到走到汇点。必然会经过第二类边经过的第一类边的数量=k层次图中找完增广路径以后，剩余图中的最短路径：2007冬令营讲座层次图中增广路径长度序列严格递增最多建n次层次图一、最短路径增值(MPLA)1=路径长度=n-12007冬令营讲座一、最短路径增值(MPLA)建层次图：复杂度分析最多有n层O(n*m)每层做一次bfs标号O(m)2007冬令营讲座一、最短路径增值(MPLA)复杂度分析找增广路：最多有n层最多找m次增广路找增广路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;ifutifoutdegree(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)程序简短对于较大规模的数据实际速度很快2007冬令营讲座三、Dinic的应用Noi2006最大获利：一共有N个通讯信号中转站，建立第i个通讯中转站需要的成本为Pi(1≤i≤N)。另有M个用户群，第i个用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1≤i≤M,1≤Ai,Bi≤N）。要求选择建立一些中转站，使得净收益最大。2007冬令营讲座解题简述：建立一张共有n+m+2个的顶点、3*m+n条边的二分图，求网络的最大流。（参考《算法艺术与信息学竞赛》p317）例题一:Profit最大获利(NOI2006)2007冬令营讲座N个点M个点源点汇点N=5000M=50000NOI2006:Profit最大获利大点数：N+M+2边数：M*3+N2007冬令营讲座Ac它贪心初始流使用高效的网络流算法2007冬令营讲座NOI2006:Profit最大获利算法的选择Test1~8test9test10最短路径增值0.1s30s30sDinic0.03s0.40s0.37s预流推进0.03s0.53s0.51sσ=0.02sDinic0.03s0.22s0.20s2007冬令营讲座例题二:矩阵游戏（2006年江苏省选拔赛）题目大意：对于一个n行、m列的0-1矩阵，规定在第i行中1的个数恰为Ri个（1=i=n）；在第j列中1的个数恰为Cj个（1=j=m）。每一行、每一列最多可以有一个格子指定为0。问是否存在一种满足条件的0-1矩阵。数据范围：n,m=1000每个测试点最多10组数据2007冬令营讲座建立二分图网络流模型把第i行作为点Xi，从S至Xi连一条边，容量为Ri把第j列作为点Yj，从Yj至T连一条边，容量为Cj若第i行第j列可以放1，那么从Xi至Yj连一条边，容量为12007冬令营讲座求网络最大流，判断流量值是否等于1的总数即可边的总数达到了O(n*m)使用MPLA可以拿到60%的分数使用Dinic可以拿到80%的分数2007冬令营讲座深入分析首先不考虑指定为0的格子因为将某2行或某2列交换，不影响问题的求解，我们不妨将Ri与Ci从大到小排序第一列，需要有6个1，但有7行可以提供1将多余的1储存起来第三列，需要5个1，但只有4行可以提供12007冬令营讲座加入这个简单的判断后，MPLA算法仍然只能过60%但是Dinic通过了100%的数据其实这题的标准方法是贪心使用高效的网络流算法节省了大部分的思考时间2007冬令营讲座四、MPM顶点u的通过量g(u)：剩余图中，入边权和与出边权和的较小值34578g(u)=122007冬令营讲座四、MPM增广时，每次找一个通过量最小的点v，从点v向源点“推”大小为g(v)的流量向汇点“拉”大小为g(v)的流量558尽量使剩余图中的边饱和2007冬令营讲座四、MPM复杂度O(n3)程序繁琐实际效果并不理想2007冬令营讲座山是山，山非山；其实困难与简单只是一线之隔2007冬令营讲座