POJ 1149 PIGS：最大流建模豬圈銷售優化

題目

M 個豬圈（初始豬數），N 個顧客（持鑰匙集合、想買數量）。顧客按序到達，打開持鑰豬圈，賣豬後可在解鎖豬圈間重新分配。求最大銷售量。
M ≤ 1000, N ≤ 100。

建模：時空展開網絡流

1. 每個顧客為一個節點，加源點 S、匯點 T。
2. 源點向**首個**擁有某豬圈鑰匙的顧客連邊，容量 = 該豬圈初始豬數。
3. 同一豬圈的**相鄰兩個**持鑰顧客間連邊，容量 = INF（可任意重新分配）。
4. 每個顧客向匯點連邊，容量 = 其購買上限。
5. 跑最大流 = 最大銷售量。

關鍵代碼片段

// 讀入豬圈初始數 a[1..M]
// 處理每個顧客 i:
vector first(M+1, 0), last(M+1, 0);
for (int i = 1; i <= N; ++i) {
    int A; cin >> A;
    vector keys(A);
    for (int k = 0; k < A; ++k) cin >> keys[k];
    int B; cin >> B; // 購買上限
    // 首次持鑰
    for (int k : keys) {
        if (!first[k]) { first[k] = i; addEdge(S, i, a[k]); }
        else { addEdge(last[k], i, INF); }
        last[k] = i;
    }
    if (B) addEdge(i, T, B);
}
cout << dinic(S, T) << endl;

複雜度

• 節點：N+2 ≤ 102，邊：O(N + M)。
• Dinic 極快，毫秒級。

小結

巧妙將「可重新分配」建模為時序上相鄰持鑰顧客間的無限容量邊，將豬圈初始存量從源點注入首個持鑰者，購買上限作為顧客到匯點容量。標準最大流模板即可解決。