edmondskarp.cpp (3)

Code này dùng cho bài toán luồng có yêu cầu về dung lượng của các nút trên mạng, mạng có nhiều điểm thu và điểm phát. (Giới hạn khả năng thông qua của các nút).

Bài toán

Cho một mạng có n nút, m cạnh (một chiều). Có ns điểm phát, nt điểm thu. Mỗi nút có một khả năng thông qua. Tìm luồng cực đại trên mạng.

Độ phức tạp

tối đa lên đến : O(n.m.m)

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

#include <stdio.h>

#include <queue>

#include <vector>

using namespace std;

#define long long long

#define in -1 + 2 *

#define out 2 *

void minimize(int &a, int b) {

    if (a > b)

        a = b;

}

void minimize(long &a, long b) {

    if (a > b)

        a = b;

}

int n, m;

vector<int> a[12309];

char b[12309];

long c[234][234];

long f[234][234];

int d[12309];

int bfs() {

    queue<int> qu;

    for (int i = 1; i <= n; i++)

        if (b[i] != 'S')

            d[i] = 0;

        else {

            d[i] = -1;

            qu.push(i);

        }

    while (qu.size()) {

        int u = qu.front();

        qu.pop();

        //printf("%d\n", u);

        if (b[u] == 'T')

            return u;

        for (int v : a[u])

            if (d[v] == 0 && c[u][v] > f[u][v]) {

                d[v] = u;

                qu.push(v);

            }

    }

    return 0;

}

long enlarge(int t) {

    //printf("enlarge(%d)\n", t);

    long delta = 1000111000111000111LL;

    int i;

    for (i = t; d[i] != -1; i = d[i])

        minimize(delta, c[d[i]][i] - f[d[i]][i]);

    for (i = t; d[i] != -1; i = d[i]) {

        f[d[i]][i] += delta;

        f[i][d[i]] -= delta;

    }

    return delta;

}

main() {

    while (scanf("%d", &n) > 0) {

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

            a[in i].clear();

            a[out i].clear();

            b[in i] = b[out i] = 0;

        }

        for (int i = 1; i <= 2 * n; i++)

            for (int j = 1; j <= 2 * n; j++)

                c[i][j] = f[i][j] = 0;

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

            int p;

            scanf("%d", &p);

            a[in i].push_back(out i);

            a[out i].push_back(in i);

            c[in i][out i] = p;

        }

        scanf("%d", &m);

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

            int p, q, w;

            scanf("%d%d%d", &p, &q, &w);

            a[out p].push_back(in q);

            a[in q].push_back(out p);

            c[out p][in q] += w;

        }

        int ns, nt;

        scanf("%d%d", &ns, &nt);

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

            int p;

            scanf("%d", &p);

            b[in p] = 'S';

        }

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

            int p;

            scanf("%d", &p);

            b[out p] = 'T';

        }

        n = n * 2;

        long r = 0;

        while (int i = bfs())

            r += enlarge(i);

        printf("%lld\n", r);

    }

}

Nhận xét

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

Với bài toán này, ta sẽ tách mỗi nút u thành hai nút u.in và u.out. u.in = 2*u-1 và u.out = 2*u.

Khả năng thông qua của nút u là c[in u][out u], khả năng thông qua của cạnh nối (u,v) là c[out u][in v].