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

BZOJ 2879 美食節：最小費用最大流 + 動態加邊優化

編輯：關於C++

題目建模

$n$ 種菜品，$m$ 位廚師。第 $i$ 種菜有 $p_i$ 份訂單。廚師 $j$ 做菜 $i$ 耗時 $t_{i,j}$。每位廚師依次制作分配給他的菜品，每份菜耗時累加。目標：分配菜品給廚師，使總等待時間最小。

等待時間公式

若廚師按順序做菜 $d_1, d_2, \dots, d_k$，則第 $x$ 份菜的等待時間 = $\sum_{y=1}^x t_{d_y}$。總等待時間 = $\sum_{x=1}^k (k-x+1) \cdot t_{d_x}$。即越早做的菜權重越大（被後續所有菜疊加）。

最小費用流建模

網絡結構

源點 S → 廚師-位置節點：每位廚師最多做 $\sum p_i$ 道菜，拆成 $p_{\text{sum}}$ 個位置節點 $(j, k)$ 表示廚師 $j$ 的第 $k$ 個製作槽位。邊容量 1、費用 0。
廚師-位置節點 → 菜品節點：廚師 $j$ 的第 $k$ 個槽位做菜 $i$，費用 = $k \cdot t_{i,j}$（權重 $k$ 乘以單份耗時）。容量 1。
菜品節點 → 匯點 T：菜品 $i$ 需求 $p_i$，邊容量 $p_i$、費用 0。

跑滿流 $\sum p_i$ 的最小費用即為答案。

動態加邊優化：避免 $O(m \cdot p_{\text{sum}} \cdot n)$ 邊爆炸

全圖邊數 = $m \cdot p_{\text{sum}} \cdot n$。$n\le 40, m\le 100, p_{\text{sum}}\le 800$ → 邊數高達 $3.2 \times 10^6$，SPFA 會 TLE。

觀察：費用遞增性

對固定廚師 $j$ 和菜品 $i$，費用 $k \cdot t_{i,j}$ 隨槽位 $k$ 遞增。最小費用流會優先使用小 $k$ 的邊。大 $k$ 的邊大概率不會被用到。

動態加邊策略

初始只連接每個廚師的 第 1 個槽位 到所有菜品（費用 $1 \cdot t_{i,j}$）。
每次增廣找到一條 $S \to (j, k) \to i \to T$ 的路徑。
增廣後，若該路徑使用了廚師 $j$ 的第 $k$ 個槽位，則動態添加該廚師第 $k+1$ 個槽位到所有菜品的邊（費用 $(k+1) \cdot t_{i,j}$）。
繼續下一輪 SPFA，直到流量滿足需求。

實際添加的邊數遠小於全圖，極大加速。

關鍵代碼片段


struct Edge { int to, cap, cost, rev; };
vector G[MAXV];
int h[MAXV], dist[MAXV], prevv[MAXV], preve[MAXV];

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

// 動態加邊：廚師 j 的第 k+1 個槽位
void addNextSlot(int chef, int slot) {
    int node = chef * Psum + slot; // Psum = sum(p_i)
    for (int dish = 1; dish <= n; ++dish) {
        addEdge(node, n*Psum + dish, 1, slot * t[dish][chef]);
    }
}

int minCostFlow(int s, int t, int maxf) {
    int res = 0;
    fill(h, h+V, 0);
    while (maxf > 0) {
        // SPFA 求最短路
        fill(dist, dist+V, INF);
        dist[s] = 0;
        queue q; q.push(s);
        vector inq(V, false); inq[s] = true;
        while (!q.empty()) {
            int v = q.front(); q.pop(); inq[v] = false;
            for (int i=0;i 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                    prevv[e.to] = v; preve[e.to] = i;
                    if (!inq[e.to]) { q.push(e.to); inq[e.to] = true; }
                }
            }
        }
        if (dist[t] == INF) return -1; // 無法滿流
        for (int v=0; v (chef, slot)
                int slotNode = v;
                int chef = slotNode / Psum;
                int slot = slotNode % Psum;
                if (slot + 1 <= Psum) addNextSlot(chef, slot + 1);
            }
        }
    }
    return res;
}