UVa - 12873 解題紀錄

題目： UVa - 12873 - The Programmers

題目說明

給 P 個隊伍、S 個賽區，每隊分別都有可以去的賽區，而每一個賽區最多容納 C 個隊伍。
請問參加的總隊伍數量最大為何？

UVa 12873 - The Programmers | Morris’ Blog

解題思路

最大流，可使用 Edmonds-Karp 求解，也可使用 Dinic。這題使用 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/fwPNIx

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

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

// source: 0, sink: P + S + 1
int P, S, C, m;
int source = 0, sink;

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

void read()
{
    cin >> P >> S >> C >> m;
    sink = P + S + 1;

    int u, v;
    while (m--)
    {
        cin >> u >> v;
        c[u][P + v] = 1;
    }

    // build edges
    FOR(i, 1, P + 1) c[source][i] = 1;
    FOR(i, 1, S + 1) c[i + P][sink] = C;
}

int augment(int u, int v, int bottleNeck)
{
    if (v == source) 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(source);
        vis[source] = true;

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

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

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

        if (!vis[sink]) break;
        mf += augment(p[sink], sink, INF);
    }

    return mf;
}

void solve()
{
    cout << maxiumFlow() << '\n';
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        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/fwPNIx

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

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

// source: 0, sink: P + S + 1
int P, S, C, m;
int source = 0, sink;

void init()
{
    CLR(rn);
}

void read()
{
    cin >> P >> S >> C >> m;
    sink = P + S + 1;

    int u, v;
    while (m--)
    {
        cin >> u >> v;
        rn[u][P + v] = 1;
    }

    // build edges
    FOR(i, 1, P + 1) rn[source][i] = 1;
    FOR(i, 1, S + 1) rn[i + P][sink] = C;
}

int augment(int u, int v, int bottleNeck)
{
    if (v == source) 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(source);
        vis[source] = true;

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

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

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

        if (!vis[sink]) break;
        mf += augment(p[sink], sink, INF);
    }

    return mf;
}

void solve()
{
    cout << maxiumFlow() << '\n';
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        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 = 530;

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

// source: 0, sink: P + S + 1
int P, S, C, m;
int source = 0, sink;

void init()
{
    CLR(rn);
}

void read()
{
    cin >> P >> S >> C >> m;
    sink = P + S + 1;

    int u, v;
    while (m--)
    {
        cin >> u >> v;
        rn[u][P + v] = 1;
    }

    // build edges
    FOR(i, 1, P + 1) rn[source][i] = 1;
    FOR(i, 1, S + 1) rn[i + P][sink] = C;
}

bool dinicBFS()
{
    CLR(l);

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

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

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

    return l[sink];
}

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

    for (int v = 1; v <= sink && 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;
}

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

void solve()
{
    cout << maxiumFlow() << '\n';
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        init();
        read();
        solve();
    }
}

參考資料

UVa 12873 - The Programmers | Morris’ Blog
Dinic算法详解及实现 - 0giant - 博客园