POJ 3281 Dining：ISAP 最大流解決奶牛飲食偏好匹配

問題建模

有 N 隻奶牛、F 種食物、D 種飲料。每隻奶牛有喜歡的食物集合和飲料集合。每種食物/飲料只能分配給一隻奶牛。目標：最大化同時獲得喜歡的食物和飲料的奶牛數。

構建網絡流圖：

• 源點 S，匯點 T。
• 食物節點 1..F，飲料節點 1..D。
• 每隻奶牛拆為兩個節點：cow_in (接食物) 和 cow_out (接飲料)，中間連容量 1 的邊。
• S → 食物 (容量 1)，飲料 → T (容量 1)。
• 食物 → cow_in (若奶牛喜歡，容量 1)。
• cow_out → 飲料 (若奶牛喜歡，容量 1)。

最大流即為答案。

ISAP 算法實現要點

• 間隙優化：維護 gap[h] 記錄距離標號為 h 的節點數，若 gap[h]==0 則提前終止（間隙斷層）。
• 當前弧優化：cur[u] 記錄下一次嘗試的邊，避免重複掃描飽和邊。
• 距離標號：dep[u] 為 u 到 T 的最短距離下界，BFS 從 T 反向初始化。
• 增廣：找到增廣路後沿 pre 回溯更新流量。

核心 C++ 代碼片段

struct Edge { int to, next, cap, flow; };
vector<Edge> E;
vector<int> G[MAXN];
int dep[MAXN], gap[MAXN], cur[MAXN], pre[MAXN];

void addEdge(int u, int v, int c) {
    E.push_back({v, (int)G[u].size(), c, 0});
    G[u].push_back(E.size()-1);
    E.push_back({u, (int)G[v].size(), 0, 0});
    G[v].push_back(E.size()-1);
}

int ISAP(int S, int T, int N) {
    fill(dep, dep+N, 0); fill(gap, gap+N, 0);
    copy(G, G+N, cur); // 當前弧初始化
    gap[0] = N;
    int u = S, flow = 0;
    pre[S] = -1;
    while (dep[S] < N) {
        if (u == T) { /* 找到增廣路，回溯更新流量 */ }
        bool adv = false;
        for (int &i = cur[u]; i < G[u].size(); i++) {
            Edge &e = E[i];
            if (e.cap > e.flow && dep[e.to] + 1 == dep[u]) {
                pre[e.to] = i; u = e.to; adv = true; break;
            }
        }
        if (adv) continue;
        // 重新標號
        int minDep = N;
        for (int i : G[u]) if (E[i].cap > E[i].flow) minDep = min(minDep, dep[E[i].to]);
        if (--gap[dep[u]] == 0) break; // 間隙優化
        dep[u] = minDep + 1; gap[dep[u]]++;
        if (u != S) u = E[pre[u]^1].to; // 退回上一節點
    }
    return flow;
}

複雜度與測試

• 節點數 ≤ F + D + 2N + 2 ≤ 502，邊數 ≤ F·N + D·N + N ≤ 20,000。
• ISAP 實測極快，POJ 3281 時限 2s，C++ 通過無壓力。

總結

POJ 3281 是「二分圖匹配推廣到三層」的經典最大流建模。ISAP 配合間隙優化、當前弧優化是解決此類中等規模最大流的首選模板。關鍵在於正確拆分奶牛節點、構建三層網絡、處理重邊去重。