您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

POJ 1149 豬圈問題：最大流經典構圖模型詳解

編輯：關於C++

題目大意

有 m 個豬圈，n 個商人。每個商人購買特定豬圈的豬。商人購買後，可從其他開著門的豬圈調豬過來。求 n 個商人最多能購買多少頭豬。

構圖核心洞察

將問題建模為最大流：

源點 S 連向每個豬圈，容量 = 該豬圈初始豬數
豬圈連向商人：關鍵在於門的開閉狀態
商人連向匯點 T，容量 = 無限大（或該商人需求量）

門的開閉與邊的構建

首次打開門的豬圈：直接連向該商人，容量 = 豬圈豬數（所有豬可賣給他）
非首次打開：找到上一個打開該豬圈門的商人，從該商人連一條容量 INF的邊到當前商人

為什麼這樣構建？ 商人購買後可調豬，相當於「上一個商人把剩豬轉給下一個商人」。INF 容量表示可轉移任意數量。首次打開門的商人直接從豬圈取豬，後續商人從前一個商人「接力」取豬。

完整 Dinic 最大流實現

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;

struct Edge {
    int to, cap, rev;
    Edge(int a, int b, int c) : to(a), cap(b), rev(c) {}
};

vector<Edge> G[MAXN];
int level[MAXN], iter[MAXN];

void addEdge(int from, int to, int cap) {
    G[from].push_back(Edge(to, cap, G[to].size()));
    G[to].push_back(Edge(from, 0, G[from].size() - 1));
}

void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0; q.push(s);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (auto &e : G[v]) {
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); ++i) {
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int maxFlow(int s, int t) {
    int flow = 0;
    while (true) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while ((f = dfs(s, t, INF)) > 0) flow += f;
    }
}

int lastBuyer[1010];  // 記錄每個豬圈上一個打開門的商人
int pigNum[1010];     // 每個豬圈豬數

int main() {
    int m, n;
    while (cin >> m >> n) {
        if (m == 0 && n == 0) break;
        
        for (int i = 1; i <= m; ++i) cin >> pigNum[i];
        
        int S = 0, T = n + 1;
        for (int i = 0; i <= T; ++i) G[i].clear();
        memset(lastBuyer, 0, sizeof(lastBuyer));
        
        // 源點連豬圈
        for (int i = 1; i <= m; ++i)
            addEdge(S, i, pigNum[i]);
        
        // 處理每個商人
        for (int buyer = 1; buyer <= n; ++buyer) {
            int k; cin >> k;
            for (int j = 0; j < k; ++j) {
                int pen; cin >> pen;
                if (lastBuyer[pen] == 0) {
                    // 首次打開：豬圈直連商人
                    addEdge(pen, m + buyer, pigNum[pen]);
                } else {
                    // 非首次：上一個商人連當前商人，容量 INF
                    addEdge(m + lastBuyer[pen], m + buyer, INF);
                }
                lastBuyer[pen] = buyer;
            }
        }
        
        // 商人連匯點
        for (int buyer = 1; buyer <= n; ++buyer)
            addEdge(m + buyer, T, INF);
        
        cout << maxFlow(S, T) << endl;
    }
    return 0;
}