UVa - 820 解題紀錄 | Larry's notes

題目說明

求 S 到 T 的最大流量為多少。網路是雙向連接的，但共用頻寬，例如 A B 10，則 A 到 B 的流量 + B 到 A 的流量要小於等於 10。另外這題給測資的方式會有可能給你很多組 A B Xi，所以 A 到 B 的頻寬要把 Xi 全部加起來，例如底下例子 1 ~ 2 的頻寬為 30。
2
1 2 2
1 2 10
1 2 20

Programming學習筆記: UVa 820 Network Bandwidth

解題思路

最大流基本題，可使用 Edmonds-Karp 求解，也可使用 Dinic。

參考解法

Edmonds-Karp:

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define CLR(c) memset(c, 0, sizeof(c))

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

template <typename T>
T QPOP(queue<T>& q)
{
    T tmp = q.front();
    q.pop();
    return tmp;
}

// reference: https://ppt.cc/fv1Gvx

const int INF = (int)1e9;
const int MXN = 101;

int f[MXN][MXN];
int c[MXN][MXN];
int p[MXN];
bool vis[MXN];

int N, S, T, C; // S: Source, T: Sink

void init()
{
    CLR(f);
    CLR(c);
}

void read()
{
    int u, v, w;
    cin >> S >> T >> C;
    while (C--)
    {
        cin >> u >> v >> w;
        c[u][v] += w;
        c[v][u] += w;
    }
}

int augment(int u, int v, int bottleNeck)
{
    if (v == S) return bottleNeck;
    bottleNeck = augment(p[u], u, min(c[u][v] - f[u][v], bottleNeck));
    f[u][v] += bottleNeck;
    f[v][u] -= bottleNeck;
    return bottleNeck;
}

// Edmonds-Karp
int maxiumFlow()
{
    int mf = 0;

    while (true)
    {
        CLR(vis);

        queue<int> q;
        q.push(S);
        vis[S] = true;

        while (!q.empty() && !vis[T])
        {
            int u = QPOP(q);

            FOR(v, 1, N + 1)
            {
                if (vis[v] || f[u][v] >= c[u][v]) continue;

                q.push(v);
                vis[v] = true;
                p[v] = u;
            }
        }

        if (!vis[T]) break; // no path
        mf += augment(p[T], T, INF);
    }

    return mf;
}

void solve()
{
    static int C = 0;
    cout << "Network " << ++C << '\n';
    cout << "The bandwidth is " << maxiumFlow() << ".\n\n";
}

int main()
{
    while (cin >> N && N)
    {
        init();
        read();
        solve();
    }
}

上面的作法將 Flow 跟 Capacity 分開，主要是希望可以保留 Capacity，若沒此需求也可以直接將一開始的 Capacity 當作 Residual Network 來做，可以省去一個陣列。

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define CLR(c) memset(c, 0, sizeof(c))

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

template <typename T>
T QPOP(queue<T>& q)
{
    T tmp = q.front();
    q.pop();
    return tmp;
}

// reference: https://ppt.cc/fv1Gvx

const int INF = (int)1e9;
const int MXN = 101;

int rn[MXN][MXN];
int p[MXN];
bool vis[MXN];

int N, S, T, C; // S: Source, T: Sink

void init()
{
    CLR(rn);
}

void read()
{
    int u, v, w;
    cin >> S >> T >> C;
    while (C--)
    {
        cin >> u >> v >> w;
        rn[u][v] += w;
        rn[v][u] += w;
    }
}

int augment(int u, int v, int bottleNeck)
{
    if (v == S) return bottleNeck;
    bottleNeck = augment(p[u], u, min(rn[u][v], bottleNeck));
    rn[u][v] -= bottleNeck;
    rn[v][u] += bottleNeck;
    return bottleNeck;
}

// Edmonds-Karp
int maxiumFlow()
{
    int mf = 0;

    while (true)
    {
        CLR(vis);

        queue<int> q;
        q.push(S);
        vis[S] = true;

        while (!q.empty() && !vis[T])
        {
            int u = QPOP(q);

            FOR(v, 1, N + 1)
            {
                if (vis[v] || !rn[u][v]) continue;

                q.push(v);
                vis[v] = true;
                p[v] = u;
            }
        }

        if (!vis[T]) break; // no path
        mf += augment(p[T], T, INF);
    }

    return mf;
}

void solve()
{
    static int C = 0;
    cout << "Network " << ++C << '\n';
    cout << "The bandwidth is " << maxiumFlow() << ".\n\n";
}

int main()
{
    while (cin >> N && N)
    {
        init();
        read();
        solve();
    }
}

Dinic:

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define CLR(c) memset(c, 0, sizeof(c))

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

template <typename T>
T QPOP(queue<T>& q)
{
    T tmp = q.front();
    q.pop();
    return tmp;
}

// reference: https://ppt.cc/fXrOUx

const int INF = (int)1e9;
const int MXN = 101;

int rn[MXN][MXN];
int l[MXN];

int N, S, T, C; // S: Source, T: Sink

void init()
{
    CLR(rn);
}

void read()
{
    int u, v, w;
    cin >> S >> T >> C;
    while (C--)
    {
        cin >> u >> v >> w;
        rn[u][v] += w;
        rn[v][u] += w;
    }
}

bool dinicBFS()
{
    CLR(l);

    queue<int> q;
    q.push(S);
    l[S] = 1;

    while (!q.empty())
    {
        int u = QPOP(q);

        FOR(v, 1, N + 1)
        {
            if (l[v] || !rn[u][v]) continue;
            l[v] = l[u] + 1;
            q.push(v);
        }
    }

    return l[T];
}

int dinicDFS(int u, int cp)
{
    if (u == T) return cp;

    int tmp = cp;

    for (int v = 1; v <= N && tmp; ++v)
    {
        if (l[v] != l[u] + 1 || !rn[u][v]) continue;
        
        int bottleNeck = dinicDFS(v, min(rn[u][v], tmp));
        rn[u][v] -= bottleNeck;
        rn[v][u] += bottleNeck;
        tmp -= bottleNeck;
    }

    return cp - tmp;
}

int maxiumFlow()
{
    int mf = 0;
    while (dinicBFS()) mf += dinicDFS(S, INF);
    return mf;
}

void solve()
{
    static int C = 0;
    cout << "Network " << ++C << '\n';
    cout << "The bandwidth is " << maxiumFlow() << ".\n\n";
}

int main()
{
    while (cin >> N && N)
    {
        init();
        read();
        solve();
    }
}

參考資料

Programming學習筆記: UVa 820 Network Bandwidth
UVa 820 - Internet Bandwidth | NaiveRed’s Blog
Dinic算法详解及实现 - 0giant - 博客园