《Dinic算法标准模板》由会员分享，可在线阅读，更多相关《Dinic算法标准模板（6页珍藏版）》请在金锄头文库上搜索。
1、传说中效率很高的最大流算法(Dinic) Dinic 是个很神奇的网络流算法。它是一个基于“层次图”的时间效率优先的 最大流算法。层次图是什么东西呢？层次，其实就是从源点走到那个点的最短路径长度。于 是乎，我们得到一个定理：从源点开始，在层次图中沿着边不管怎么走，经过 的路径一定是终点在剩余图中的最短路。（摘自 WC2007 王欣上论文）注意，这 里是要按照层次走。那么，MPLA（最短路径增值）的一大堆复杂的证明我就略掉了，有兴趣的请自 行参阅 WC2007 王欣上神牛的论文。首先我们得知道，Dinic 的基本算法步骤是，先算出剩余图，然后用剩余图算 层次图，然后在层次图里找增广路。不知道你想
2、到没有，这个层次图找增广路 的方法，恰恰就是 Ford-Fulkerson 类算法的时间耗费最大的地方，就是找一个 最短的增广路。所以呢，层次图就相当于是一个已经预处理好的增广路标志图。如何实现 Dinic 呢？首先我们必然要判一下有没有能到达终点的路径（判存在增广路与否），在这 个过程中我们顺便就把层次图给算出来了（当然不用算完），然后就沿着层次 图一层一层地找增广路；找到一条就进行增广（注意在沿着层次图找增广路的 时候使用栈的结构，把路径压进栈）；增广完了继续找，找不到退栈，然后继 续找有没有与这个结点相连的下一层结点，直到栈空。如果用递归实现，这个 东西就很好办了，不过我下面提供的程序是
3、用了模拟栈，当然这样就不存在结 点数过多爆栈的问题了不过写起来也麻烦了一些，对于“继续找”这个过 程我专门开了一个数组存当前搜索的指针。上面拉拉杂杂说了一大堆，实际上在我的理解中，层次图就是一个流从高往低 走的过程（这玩意儿有点像预流推进的标号法我觉得），在一条从高往低 的路径中，自然有些地方会有分叉；这就是 Dinic 模拟栈中退栈的精华。这就 把 BFS 的多次搜索给省略了不说，时间效率比所谓的理论复杂度要高得多。这里有必要说到一点，网络流的时间复杂度都是很悲观的，一般情况下绝对没 有可能到达那个复杂度的。DinicDinic 算法算法Dinic 算法的思想是为了减少增广次数，建立一个辅助
4、网络 L，L 与原网络 G 具有相同的节点数，但边上的容量有所不同，在 L 上进行增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流。分层的目的是降低寻找增广路的代价。算法步骤如下：STEP1：建造原网络 G 的一个分层网络 L。STEP2：用增广路算法计算 L 的最大流 F，若在 L 中找不到增广路，算法结束。SETP3：根据 F 更新 G 中的流 f，转 STEP1。分层网络的构造算法：STEP1：标号源节点 s，Ms0。STEP2：调用广度优先遍历算法，执行一步遍历操作，当前遍历的弧 e=v1v2，令rG.u（e）G.f（e）。若 r0，则（1） 若 Mv
5、2还没有遍历，则 Mv2=Mv1+1，且将弧 e 加入到 L 中，容量L.u（e）r。（2） 若 Mv2已经遍历且 Mv2=Mv1+1，则将边 e 加入到 L 中，容量L.u（e）r。（3） 否则 L.u（e）0。 否则 L.u（e）0。重复本步直至 G 遍历完。其中的 G.u(e)、G.f(e)、L.u(e)分别表示图 G 中弧 e 的容量上界和当前流量，图 L 中弧 e 的容量上界。算法的时间复杂度为 O(mn2)。其中 m 为弧的数目，是多项式算法。邻接表表示图，空间复杂度为 O(n+m)。*/ #include usingusing namespacenamespace std; ;
6、constconst longlong maxn= =300; ; constconst longlong maxm= =300000; ; constconst longlong inf= =0x7fffffff; ; structstruct node longlong v, ,next; ;longlong val; ; s maxm* *2; longlong level maxn,p maxn,que maxn,out maxn,ind; ; voidvoid init()() ind= =0; ;memset( (p,-,-1, ,sizeofsizeof( (p);); inli
7、neinline voidvoid insert( (longlong x, ,longlong y, ,longlong z) ) s ind.v= =y; ;s ind.val= =z; ;s ind.next= =p x;p x=ind+;+;s ind.v= =x; ;s ind.val= =0; ;s ind.next= =p y;p y=ind+;+; longlong max_flow( (longlong n, ,longlong source, ,longlong sink) ) longlong ret= =0; ;longlong h= =0, ,r= =0; ;whil
8、ewhile( (1) ) longlong i; ;forfor( (i= =0; ;i=0) ) que+q=cur; ;out source=s cur.next; ; elseelse breakbreak; ; longlong u= =s que q.v; ;ifif( (u=sink) ) longlong dd= =inf; ;longlong index=-=-1; ;forfor( (i= =0; ;i s que i.val) ) dd= =s que i.val; ;index= =i; ; ret+=+=dd; ;/coutretendl;forfor( (i= =0
9、; ;i=q; ;i+)+) s que i.val-=-=dd; ;s que i1.val+=+=dd; ; forfor( (i= =0; ;i=q; ;i+)+) ifif( (s que i.val=0) ) q= =index- -1; ;breakbreak; ; elseelse longlong cur= =out u;forfor(;(;cur!=-!=-1; ;cur= =s cur.next) ) ifif( (s cur.val ; ifif( (cur!=-!=-1) ) que+q=cur; ;out u=s cur.next; ; elseelse out u=
10、-=-1; ;q-;-; returnreturn ret; ; longlong m, ,n; ;intint mainmain()() whilewhile( (scanf( (“%ld %ld“,();forfor( (intint i= =0; ;i m; ;i+)+) longlong from, ,to, ,cost; ;scanf( (“%ld %ld %ld“,);insert(-(-from,-,-to, ,cost);); longlong Start, ,End; ;Start= =1; ;End= =n; ;/ scanf(“%ld %ld“,printf( (“%ldn“, ,max_flow( (n,-,-Start,-,-End);); returnreturn 0; ;
