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

POJ 1149 PIGS：最大流模型的巧妙構造

編輯：C++ 入門

問題場景

M 個豬圈，每圈初始有若干豬。N 個顧客依次到來，每位顧客打開指定的若干豬圈，從中購買豬（有購買上限）。顧客離開後，其打開的豬圈間可以任意調豬，隨後所有豬圈關閉。求最多能賣出多少頭豬。（N ≤ 100, M ≤ 1000）

網絡流建模核心思想

將「豬的流動」建模為流：「源點 → 第一個打開該豬圈的顧客（容量=初始豬數）→ 同一豬圈的相鄰顧客間（容量=∞）→ 每位顧客 → 匯點（容量=購買上限）」。

具體構造規則

每位顧客一個節點。
對每個豬圈，找到第一個打開它的顧客，從源點向該顧客連邊，容量 = 豬圈初始豬數；若多個豬圈第一個顧客相同，合併邊（容量相加）。
對每個豬圈，按顧客到達順序排序，從第 i 個顧客向第 i+1 個顧客連容量 ∞ 的邊，表示豬可在開放豬圈間自由流動。
每位顧客向匯點連邊，容量 = 該顧客購買上限。

Dinic 算法實現

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

const int MAXN = 1050;
const int INF = 1e9;

struct Edge { int from, to, cap, flow; };
struct Dinic {
    int n, s, t;
    vector<Edge> edges;
    vector<int> G[MAXN];
    bool vis[MAXN];
    int d[MAXN], cur[MAXN];

    void init(int n) { this->n = n; for (int i=0;i<=n;++i) G[i].clear(); edges.clear(); }
    void addEdge(int u, int v, int c) {
        edges.push_back({u, v, c, 0});
        edges.push_back({v, u, 0, 0});
        int m = edges.size();
        G[u].push_back(m-2); G[v].push_back(m-1);
    }
    bool bfs() {
        memset(vis, 0, sizeof vis);
        queue<int> q; q.push(s); vis[s]=1; d[s]=0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i : G[x]) {
                Edge &e = edges[i];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to]=1; d[e.to]=d[x]+1; q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x, int a) {
        if (x==t || a==0) return a;
        int flow=0, f;
        for (int &i=cur[x]; i<(int)G[x].size(); ++i) {
            Edge &e = edges[G[x][i]];
            if (d[x]+1==d[e.to] && (f=dfs(e.to, min(a, e.cap-e.flow)))>0) {
                e.flow+=f; edges[G[x][i]^1].flow-=f;
                flow+=f; a-=f; if (a==0) break;
            }
        }
        return flow;
    }
    int maxFlow(int s, int t) {
        this->s=s; this->t=t; int flow=0;
        while (bfs()) { memset(cur,0,sizeof cur); flow+=dfs(s,INF); }
        return flow;
    }
};

Dinic gao;
int pig[MAXN], pre[MAXN];

void solve() {
    int A, B, K;
    int s = 0, t = n + 1;
    gao.init(t+2);
    memset(pre, 0, sizeof pre);
    for (int i=1;i<=m;++i) scanf("%d", &pig[i]);
    for (int i=1;i<=n;++i) {
        scanf("%d", &A);
        for (int j=1;j<=A;++j) {
            scanf("%d", &K);
            if (!pre[K]) gao.addEdge(s, i, pig[K]);
            else gao.addEdge(pre[K], i, INF);
            pre[K] = i;
        }
        scanf("%d", &B);
        gao.addEdge(i, t, B);
    }
    printf("%d\n", gao.maxFlow(s, t));
}

int main() {
    while (~scanf("%d%d", &m, &n)) solve();
    return 0;
}