最大流算法小结

tezuka158

   最近在看网络流，把几个常用的算法总结下，正确性的证明和一些理论的东西就不写了，参看算法导论和神牛们的论文，我只写算法的理解和实现模板。
Ford-Fulkerson方法
      每次找增广路，把这条路上的所有点的流量加上这条路上的残余容量，再找新的增广路，直到找不到为止，它有很多种实现方法，下面给出算法导论上的伪代码


Ford_Fulkerson( G, s, t ){

    for each edge( u, v )∈E[G]

        do    f[u,v]= 0

            f[v,u]= 0

    while there exists a path p from s to t in the residual network Gf


        do    Cf(p)= min{ Cf(u,v) | (u,v) is in p }

        for each edge(u,v) in p

            do    f[u,v]+= Cf(p)

                f[v,u]= -f[u,v]
Edmonds-Karp算法
      就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE2)
      (代码参考NOCOW)

#define VMAX 201

int n, m;        //分别表示图的边数和顶点数

int c[VMAX][VMAX];


int Edmonds_Karp( int s, int t ){    //输入源点和汇点

    int p, q, queue[VMAX], u, v, pre[VMAX], flow= 0, aug;


    while(true){

        memset(pre,-1,sizeof(pre));        //记录父节点


        for( queue[p=q=0]=s; pq; p++ ){    //广度优先搜索

            u= queue[p];

            for( v=0; v&&pre[t]0; v++ )

                if( c[v]>0 && pre[v]0 )

                    pre[v]=u, queue[++q]=v;

            if( pre[t]>=0 )    break;

        }

        if( pre[t]0 )    break;        //不存在增广路

        aug= 0x7fff;    //记录最小残留容量

        for( u=pre[v=t]; v!=s; v=u,u=pre )

            if(c[v]aug)    aug=c[v];

        for( u=pre[v=t]; v!=s; v=u,u=pre )

            c[v]-=aug, c[v]+=aug;

        flow+= aug;

    }

    return flow;

}
Push-Relabel算法
Relabel-to-Front算法
Preflow-Push算法
Dinic算法
先放着，慢慢写……
http://evalls.yo2.cn/articles/preflow_push.html
http://www.stubc.com/thread-3665-1-1.html
http://cuitianyi.com/blog/%E6%B1%82%E6%9C%80%E5%A4%A7%E6%B5%81%E7%9A%84relabel-to-front%E7%AE%97%E6%B3%95/
http://blog.sina.com.cn/s/blog_5774b8650100cnjc.html
http://www.nocow.cn/index.php/%E7%BD%91%E7%BB%9C%E6%B5%81#.E7.BB.83.E4.B9.A0.E9.A2.98.E7.9B.AE
http://hi.baidu.com/_green_hand_/blog/item/0d1715250b6f5435c9955917.html
http://blog.csdn.net/soberman/archive/2009/03/09/3974871.aspx
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76848/showart_1999661.html