程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [POJ 1149] PIGS (網絡流最大流）

[POJ 1149] PIGS (網絡流最大流）

編輯：C++入門知識

PIGS

題目鏈接：http://poj.org/problem?id=1149

題目大意：

邁克有個養豬場，養豬場裡有M個豬圈，每個豬圈都上了鎖。邁克沒有鑰匙，而要買豬的顧客一個接一個來到養豬場，每個顧客有一些豬圈的鑰匙，要買一定數量的豬。當每個顧客來時，將有鑰匙的豬圈全部打開，從中挑出一些買走，然後邁克可以重新分配這些豬圈裡面的豬。當顧客離開後，門又被鎖上。問邁克最多可以賣多少豬。

解題思路：

網絡流的題目難就難在建圖，這道題目的建圖是這樣的：

/*
ID: [email protected]
PROG:
LANG: C++
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define maxn 1000
#define maxm 10000
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
using namespace std;
int M, N, A, K, B;
int pig[maxn + 10] = {0};
int has[maxn + 10] = {0};
struct node {
    int v, f, nxt;
}e[maxm * 2 + 10];
int g[maxn] = {0}, cnt, st = 0, ed;

void add(int u, int v, int c) {
    e[++cnt].v = v;
    e[cnt].f = c;
    e[cnt].nxt = g[u];
    g[u] = cnt;
    e[++cnt].v = u;
    e[cnt].f = 0;
    e[cnt].nxt = g[v];
    g[v] = cnt;
}

void init() {
    cnt = 1;
    ed = N + 1;
    for (int i = 1; i <= M; i++) scanf("%d", pig + i);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &A);
        int sum = 0;
        while(A--) {
            scanf("%d", &K);
            if (!has[K]) sum += pig[K];
            else add(has[K], i, INF);
            has[K] = i;
        }
        add(st, i, sum);
        scanf("%d", &B);
        add(i, ed, B);
    }
}

int dis[maxn + 10], vis[maxn + 10], q[maxn + 10];

void bfs() {
    mem(dis, 0);
    int font = 0, rear = 1;
    q[font] = st;
    vis[st] = 1;
    while(font < rear) {
        int u = q[font++];
        for (int i = g[u]; i; i = e[i].nxt) if (e[i].f && !vis[e[i].v]) {
            vis[e[i].v] = 1;
            q[rear++] = e[i].v;
            dis[e[i].v] = dis[u] + 1;
        }
    }
}

int dfs(int u, int delta) {
    if (u == ed) return delta;
    else {
        int ret = 0;
        for (int i = g[u]; i && delta; i = e[i].nxt) if (e[i].f && dis[e[i].v] == dis[u] + 1) {
            int dd = dfs(e[i].v, min(delta, e[i].f));
            e[i].f -= dd;
            e[i ^ 1].f += dd;
            delta -= dd;
            ret += dd;
        }
        return ret;
    }
}
int maxflow() {
    int ret = 0;
    while(1) {
        mem(vis, 0);
        bfs();
        if (!vis[ed]) return ret;
        ret += dfs(st, INF);
    }
}
int main ()
{
    scanf("%d%d", &M, &N);
    init();
    printf("%d\n", maxflow());
    return 0;
}

（1）將顧客看做是除了源點和匯點以外的結點，並且另外設兩個結點：源點和匯點。（2）源點和每個豬圈的第1個顧客連邊，邊的權是開始時豬圈中豬的數量。（3）若源點和每個結點之間有重邊，可以合並。（4）顧客j緊跟顧客i之後打開豬圈，則邊的權是正無窮大，因為如果j緊跟i之後打開，邁克可以根據j的需求將其他豬圈調到該豬圈，這樣顧客j就可以買到盡可能多的豬。（5）每個顧客和匯點之間連邊，表示顧客希望買豬的數目。
這樣題目就成了基礎的網絡最大流。