糯米

Dinic算法是一種比較容易實(shí)現(xiàn)的，相對(duì)比較快的最大流算法。
今天看了一下它的原理，發(fā)現(xiàn)的確很牛逼。

求最大流的本質(zhì)，就是不停的尋找增廣路徑。直到找不到增廣路徑為止。
對(duì)于這個(gè)一般性的過程，Dinic算法的優(yōu)化如下：

（1）
Dinic算法首先對(duì)圖進(jìn)行一次BFS，然后在BFS生成的層次圖中進(jìn)行多次DFS。
層次圖的意思就是，只有在BFS樹中深度相差1的節(jié)點(diǎn)才是連接的。
這就切斷了原有的圖中的許多不必要的連接。很牛逼！
這是需要證明的，估計(jì)證明也很復(fù)雜。

（2）
除此之外，每次DFS完后，會(huì)找到路徑中容量最小的一條邊。
在這條邊之前的路徑的容量是大于等于這條邊的容量的。
那么從這條邊之前的點(diǎn)，可能引發(fā)出別的增廣路徑。
比如說 S -> b -> c -> d -> T 是一條增廣路徑，容量最小的邊是 b -> c。
可能存在一條 S -> b -> e -> f -> g -> T 這樣的增廣路徑。
這樣的話，在找到第一條增廣路徑后，只需要回溯到 b 點(diǎn)，就可以繼續(xù)找下去了。
這樣做的好處是，避免了找到一條路徑就從頭開始尋找另外一條的開銷。
也就是再次從 S 尋找到 b 的開銷。
這個(gè)過程看似復(fù)雜，但是代碼實(shí)現(xiàn)起來很優(yōu)雅，因?yàn)樗谋举|(zhì)就是回溯！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_VETXS 1024
#define MAX_EDGES 1024

int E[MAX_EDGES], next[MAX_EDGES], C[MAX_EDGES], M;
int V[MAX_VETXS], L[MAX_VETXS], Q[MAX_VETXS], N;
int S, T;

void __insert(int from, int to, int cap)
{
    M++;
    C[M] = cap;
    E[M] = to;
    next[M] = V[from];
    V[from] = M;
}

void insert(int from, int to, int cap)
{
    __insert(from, to, cap);
    __insert(to, from, 0);
}

int bfs()
{
    int h, t, e, u, v;

    h = t = 0;
    Q[t++] = S;
    memset(L, 0, N*sizeof(L[0]));
    L[S] = 1;
    while (h != t) {
        u = Q[h++];
        for (e = V[u]; e; e = next[e]) {
            v = E[e];
            if (!L[v] && C[e] > 0) {
                L[v] = L[u] + 1;
                Q[t++] = v;
            }
        }
    }

    return L[T];
}

int dfs()
{
    int t, u, v, e, i, f, r, back;

    t = 1;
    r = 0;

    while (t) {
        u = (t == 1) ? S : E[Q[t - 1]];
        if (u == T) {
            f = INT_MAX;
            for (i = 1; i < t; i++) {
                e = Q[i];
                if (C[e] < f) {
                    f = C[e];
                    back = i;
                }
            }
            for (i = 1; i < t; i++) {
                e = Q[i];
                C[e] -= f;
                C[e^1] += f;
            }
            r += f;
            t = back;
        } else {
            for (e = V[u]; e; e = next[e]) {
                v = E[e];
                if (L[v] == L[u] + 1 && C[e] > 0)
                    break;
            }
            if (e)
                Q[t++] = e;
            else {
                t--;
                L[u] = 0;
            }
        }
    }

    return r;
}

int dinic()
{
    int f = 0;

    while (bfs())
        f += dfs();

    return f;
}

int main()
{
    int n, m, a, b, c, i;

    freopen("d:\\in.txt", "r", stdin);

    while (scanf("%d%d", &n, &m) != EOF) {
        S = 0;
        T = m - 1;
        N = m;
        memset(V, 0, N*sizeof(V[0]));
        M = 2;
        for (i = 0; i < n; i++) {
            scanf("%d%d%d", &a, &b, &c);
            insert(a - 1, b - 1, c);
        }
        printf("%d\n", dinic());
    }

    return 0;
}