【转载】网络流入门—用于最大流的Dinic算法 - dblank

【转载】网络流入门—用于最大流的Dinic算法

“网络流博大精深”—sideman语 <figure id="attachment_572" class="wp-caption alignright">Drainage Ditches <figcaption class="wp-caption-text">一个基本的网络流问题</figcaption></figure>感谢WHD的大力支持

最早知道网络流的内容便是最大流问题,最大流问题很好理解:

解释一定要通俗!

如右图所示,有一个管道系统,节点{1,2,3,4},有向管道{A,B,C,D,E},即有向图一张. [1]是源点,有无限的水量,[4]是汇点,管道容量如图所示.试问[4]点最大可接收的水的流量?

这便是简单的最大流问题,显然[4]点的最大流量为50

死理性派请注意:流量是单位时间内的,总可以了吧!

然而对于复杂图的最大流方法是什么呢,有EK,Dinic,SAP,etc.下面介绍Dinic算法(看代码的直接点这)
<span id="more-568"></span>
<h2>Dinic 算法</h2>
<h6>Dinic算法的基本思路:</h6>

  1. 根据残量网络计算层次图。
  2. 在层次图中使用DFS进行增广直到不存在增广路
  3. 重复以上步骤直到无法增广

<h6>小贴士:</h6>
一般情况下在Dinic算法中,我们只记录某一边的剩余流量.

  • 残量网络:包含反向弧的有向图,Dinic要循环的,每次修改过的图都是残量网络,
  • 层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为一层,(比如上图的分层为{1},{2,4},{3})
  • DFS:这个就不用说了吧…
  • 增广  :在现有流量基础上发现新的路径,扩大发现的最大流量(注意:增加量不一定是这条路径的流量,而是新的流量与上次流量之差)
  • 增广路:在现有流量基础上发现的新路径.(快来找茬,和上一条有何不同?)
  • 剩余流量:当一条边被增广之后(即它是增广路的一部分,或者说增广路通过这条边),这条边还能通过的流量.
  • 反向弧:我们在Dinic算法中,对于一条有向边,我们需要建立另一条反向边(弧),当正向(输入数据)边剩余流量减少I时,反向弧剩余流量增加I

<h6>Comzyh的较详细解释(流程) :</h6>
<figure id="attachment_567" class="wp-caption alignright">
<div class="fluid-width-video-wrapper"><object id="fitvid800825" width="300" height="150" classid="clsid:d27cdb6e-ae6d-11cf-96b8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,40,0"></object></div>
<figcaption class="wp-caption-text">Dinic动画演示</figcaption></figure>

  1. 用BFS建立分层图  注意:分层图是以当前图为基础建立的,所以要重复建立分层图
  2. 用DFS的方法寻找一条由源点到汇点的路径,获得这条路径的流量I 根据这条路径修改整个图,将所经之处正向边流量减少I,反向边流量增加I,注意I是非负数
  3. 重复步骤2,直到DFS找不到新的路径时,重复步骤1

注意(可以无视):

  • Dinic(其实其他的好多)算法中寻找到增广路后要将反向边增加I
  • Dinic中DFS时只在分层图中DFS,意思是说DFS的下一个节点的Dis(距源点的距离)要比自己的Dis大1,例如在图1中第一个次DFS中,1->2->4 这条路径是不合法的,因为Dis[2]=1;Dis[4]=1;
  • 步骤2中“获得这条路径的流量I “实现:DFS函数有参量low,代表从源点到现在最窄的(剩余流量最小)的边的剩余流量,当DFS到汇点是,Low便是我们要的流量I

<h6>对于反向弧(反向边)的理解:</h6>
这一段不理解也不是不可以,对于会写算法没什么帮助,如果你着急,直接无视即可.
先举一个例子(如右图):

<figure id="attachment_573" class="wp-caption alignright">必须使用反向弧的流网络
<figcaption class="wp-caption-text">必须使用反向弧的流网络</figcaption></figure>在这幅图中我们首先要增广1->2->4->6,这时可以获得一个容量为2的流,但是如果不建立4->2反向弧的话,则无法进一步增广,最终答案为2,显然是不对的,然而如果建立了反向弧4->2,则第二次能进行1->3->4->2->5->6的增广,最大流为3.

Comzyh对反向弧的理解可以说是”偷梁换柱“,请仔细阅读:在上面的例子中,我们可以看出,最终结果是1->2->5->6和1->2->4->6和1->3->4->6.当增广完1->2->4->5(代号A)后,在增广1->3->4->2->5->6(代号B),相当于将经过节点2的A流从中截流1(总共是2)走2->5>6,而不走2->4>6了,同时B流也从节点4截流出1(总共是1)走4->6而不是4->2->5->6,相当于AB流做加法.

简单的说反向弧为今后提供反悔的机会,让前面不走这条路而走别的路.

HDU 3549 Flow Problem

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 100;
const int maxm = 30000 + 5;
const long long INF = 0x3f3f3f;

struct Edge {
    int from, to, cap, flow;
    Edge(){}
    Edge(int from, int to, int cap, int flow) {
        this->from = from;
        this->to = to;
        this->cap = cap;
        this->flow = flow;
    }
};

struct Dinic {
    int n, m, s, t;
    Edge edges[maxm];
    int head[maxn];
    int nxt[maxm];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void init(int n) {
        this -> n = n;
        memset(head, -1, sizeof(head));
        m = 0;
    }

    void AddEdge(int u, int v, int c) {
        edges[m] = Edge(u, v, c, 0);
        nxt[m] = head[u];
        head[u] = m++;
        edges[m] = Edge(v, u, 0, 0);
        nxt[m] = head[v];
        head[v] = m++;
    }

    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i = head[x]; i != -1; i = nxt[i]) {
                Edge& e = edges[i];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x, int a) {
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i != -1; i = nxt[i]) {
            Edge& e = edges[i];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) {
                e.flow += f;
                edges[i^1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s, int t) {
        this -> s = s; this -> t = t;
        int flow = 0;
        while (BFS()) {
            for (int i = 1; i <= n; i++)
                cur[i] = head[i];
            flow += DFS(s, INF);
        }
        return flow;
    }
} H;

int main() {
    //freopen("in.txt", "r", stdin);
    int n, m, u, v, c, i, t;
    scanf("%d", &t);
    for (int ii = 1; ii <= t; ii++) {
        scanf("%d%d", &n, &m);
        H.init(n);
        for(i=1; i<=m; ++i) {
            scanf("%d%d%d", &u, &v, &c);
            H.AddEdge(u, v, c);
        }
        printf("Case %d: %dn", ii, H.Maxflow(1, n));
    }
    return 0;
}

 

相关文章

发表新评论