首页 > 代码库 > 北大ACM暑期培训课程目录(五)

北大ACM暑期培训课程目录(五)

本文出自:http://blog.csdn.net/svitter


netFlow

    Ford-Fulkerson

    深度优先搜索,制作一个流网络。

    部分路径可能不合理。



    对上次dfs的边就行重新筛选。每条边来个反向边。

    再来一次dfs

    发现还能找到一条路径。

    

    dfs->abtray edge->dfs

    stop when no new stream



    容量相等。



   *残余网络

    

        寻找变数最少的增广路径

        通过bfs寻找增广路劲

    Edmonds-Karp最短增广路算法

        依然不是很好的算法。

        POJ1273模板题

    

    Dinic快速网络流算法

        有方向的DFS(deep find search?)

        1.首先利用bfs分层

        2.必须走下一层节点。

        3.回溯。

        4.回溯原点,dfs结束。

        5.重新分层。(若无法走到汇点,算法结束)否则,返回1.

        复杂度n*n*m



    以上是最大流

    

最大流每条边上的流量,最大是多少。

    把原图备份,再减去最大流的流量。




最大流和上下界的部分待日后补充。