ini算法标准模板.doc

传说中效率很高的最大流算法（D i n i c） Dinic是个很神奇的网络流算法。它是一个基于“层次图”的时间效率优先的最 大流算法。 层次图是什么东西呢？层次，其实就是从源点走到那个点的最短路径长度。于是 乎，我们得到一个定理：从源点开始，在层次图中沿着边不管怎么走，经过的路 径一定是终点在剩余阁中的最短路。（摘自WC2007王欣上论文）注意，这里是 要按照层次走。 那么，MPLA （最短路径增值）的一大堆复杂的证明我就略掉了，有兴趣的请自行 参阅WC2007王欣上神牛的论文。 首先我们得知道，Dinic的基本算法步骤是，先算出剩余图，然后用剩余图算层 次图，然后在层次图里找增广路。不知道你想到没有，这个层次图找增广路的方 法，恰恰就是Ford-Fulkerson类算法的时间耗费最大的地方，就是找一个最短 的增广路。所以呢，层次图就相当于是一个已经预处理好的增广路标志图。 如何实现Dinic呢? 首先我们必然要判一下有没有能到达终点的路径（判存在增广路与否），在这个 过程中我们顺便就把层次阁给算出来了（当然不用算完），然后就沿着层次阁一 层一层地找增广路：找到一条就进行增广（注意在沿着层次图找增广路的时候使 用栈的结构，把路径压进栈）；增广完了继续找，找不到退栈，然后继续找有没 有与这个结点相连的下一层结点，直到栈空。如果用递归实现，这个东西就很好 办丫，不过我下面提供的程序是用Y模拟栈，当然这样就不存在结点数过多爆栈 的问题了……不过写起来也麻烦了一些，对于“继续找”这个过程我专门开了一 个数组存当前有哪些信誉好的足球投注网站的指针。 上面拉拉杂杂说了一大堆，实际上在我的理解中，层次图就是一个流从高往低走 的过程（这玩意儿有点像预流推进的标号法……我觉得），在一条从高往低的路 径屮，自然有些地方会有分叉；这就是Dinic模拟桟中退桟的精华。这就把BFS 的多次有哪些信誉好的足球投注网站给省略了不说，时间效率比所谓的理论复杂度要高得多。 这里有必要说到一点，网络流的时间复杂度都是很悲观的，一般情况下绝对没有 可能到达那个复杂度的。 Dinic算法 Dinic算法的思想是为丫减少增广次数，建立一个辅助咧络L, L与原网络G具有相同的节 点数，但边上的容景有所不同，在L上进行增广，将增广后的流值回写到原网络上，再建立当前 M络的辅助网络，如此反S,达到最大流。分层的目的是降低寻找增广路的代价。 算法步骤如下： STEP1：建造原网络G的一个分层网络L。 STEP2：用堝广路算法U?算L的最大流F,若在L中找不到增广路，算法结朿。 SETP3：根据F更新G中的流f,转STEP1。 分层网络的构造算法： STEP1：标号源节点s, M[s]=O。 STEP2：调用广度优先遍历算法，执行一步遍历操作，当前遍历的弧euo令1、=(;. u(e) —G. f (e)。 若r〉0,则 若M[v2]还没有遍历，贝(J M[v2]=M[Vi]+1,且将弧e加入到L中，容量L. u (e) =r0 若M[v2]己经遍历且M[v2]=M[Vi]+1，则将边e加入到L中，容量L. u(e) =r。 否则 L. u (e) =0o 否则 L. u (c) =0。 重复本步直至G遍历完。其中的G.u(c)、G.f(c)、L.u(e)分别表示图G中弧c的 容最上界和当前流景，图L屮弧e的容景上界。 算法的时间复杂度为0(mn2)。其中m为弧的数0,是多项式算法。邻接表表示图，空 间复杂度为0(n+m)。 ncludei ostream using namespace std; const long maxn=300; const long maxm=300000; const long inf=0x7fffffff; struct node { long v,next; long val; Is[maxm*2]; long level[maxn], p[maxn], que[maxn]，out[maxn], ind; void init () ind=0; memset (p，-1, sizeof (p)); } inline void insert (long x,long y, long 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++; } long max_flow(long n, long source, long sink) { long ret=0; long h=0, r=0; while (l) { long i; for (i=0;i〈n;++i) level[i]=0; h=0,r=0