dinitz.cpp

Bài toán

Tìm luồng cực đại trên đồ thị dùng thuật toán Dinitz.

Độ phức tạp

O(n2m)

Code này của Nguyễn Tiến Trung Kiên

#include <bits/stdc++.h>

using namespace std;

const int N = 1003, oo = 0x3c3c3c3c;

int n, m, S, T;

int d[N], c[N][N], f[N][N];

int Dfs[N], t = 0;

vector<int> a[N];

bool bfs(int S, int T) {

    memset(d, 0, sizeof d);

    queue<int> qu;

    qu.push(S);

    d[S] = 1;

    while (qu.size()) {

        int u = qu.front();

        qu.pop();

        if (u == T)

            return true;

        for (int v : a[u])

            if (!d[v] && f[u][v] < c[u][v]) {

                qu.push(v);

                d[v] = d[u] + 1;

            }

    }

    return false;

}

int visit(int u, int Min) {

    if (u == T)

        return Min;

    if (Dfs[u] != t)

        Dfs[u] = t;

    else

        return 0;

    for (int v : a[u])

        if (f[u][v] < c[u][v])

            if (Dfs[v] != t && d[v] == d[u] + 1)

                if (int x = visit(v, min(Min, c[u][v] - f[u][v]))) {

                    f[u][v] += x;

                    f[v][u] -= x;

                    return x;

                }

    return 0;

}

main() {

    cin >> n >> m >> S >> T;

    for (int i = 1; i <= m; i++) {

        int x, y, z;

        scanf("%d%d%d", &x, &y, &z);

        a[x].push_back(y);

        a[y].push_back(x);

        c[x][y] += z;

    }

    int Sum = 0;

    while (bfs(S, T)) {

        while (int x = (t++, visit(S, oo))) {

            Sum += x;

            //printf("Sum=%d\n", Sum);

        }

    }

    cout << Sum << endl;

}

Nhận xét

Code này đã được dùng để nộp cho một bài trên SPOJ.

Tham khảo

http://vn.spoj.com/problems/NKFLOW/

https://codeforces.com/group/FLVn1Sc504/contest/274823/problem/Z

https://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Dinitz