2674. 「NOI2012」美食节 题解

题目分析

我们有 $n$ 种菜品，第 $i$ 种菜品需要做 $p_i$ 份；有 $m$ 个厨师，第 $j$ 个厨师做第 $i$ 种菜品需要时间 $t_{i,j}$。每个厨师按顺序做菜，如果一个同学点的菜是某个厨师做的第 $k$ 道菜，他的等待时间就是这个厨师制作前 $k$ 道菜的时间之和。目标是最小化总等待时间。

关键观察：如果厨师 $j$ 的第 $k$ 道菜是菜品 $i$，那么：

• 这道菜本身的时间是 $t_{i,j}$
• 它会贡献给后面所有等待的同学，即它会出现在前 $k$ 道菜中
• 因此，这道菜对总等待时间的贡献是 $k \times t_{i,j}$

---

网络流建模

这是一个分配问题：将 $p = \sum p_i$ 道菜分配给 $m$ 个厨师的不同位置，最小化总费用。

1. 基本建图想法

朴素想法：

• 源点 → 菜品节点：容量 $p_i$，费用 0
• 菜品节点 → 厨师-位置节点：容量 1，费用 $k \times t_{i,j}$
• 厨师-位置节点 → 汇点：容量 1，费用 0

但这样需要 $m \times p$ 个厨师位置节点（$p$ 可达 800，$m$ 可达 100，总共 $8 \times 10^4$ 节点，边更多），会超时超内存。

2. 优化：动态加边

重要观察：

• 每个厨师的位置节点是按顺序使用的（第 1 道，第 2 道，...）
• 如果厨师还没有做第 $k$ 道菜，那么他肯定不会做第 $k+1$ 道菜
• 所以我们可以在需要时才添加新的位置节点

动态加边策略：

1. 初始时，为每个厨师只添加第 1 个位置节点
2. 每次费用流增广后，如果有厨师做了第 $k$ 道菜（使用了第 $k$ 个位置节点）
3. 则为该厨师添加第 $k+1$ 个位置节点和相关边
4. 继续增广，直到所有菜品分配完毕

---

详细建模

节点编号设计

• 源点：$0$
• 菜品节点：$1..n$
• 厨师位置节点：动态添加，从 $n+1$ 开始
• 汇点：最后一个节点

初始建图

1. 源点 → 菜品 $i$：容量 $p_i$，费用 $0$
2. 为每个厨师 $j$ 创建第 1 个位置节点 $node_{j,1}$
   • 菜品 $i$ → $node_{j,1}$：容量 $1$，费用 $1 \times t_{i,j}$
   • $node_{j,1}$ → 汇点：容量 $1$，费用 $0$

动态加边过程

1. 运行一次最小费用最大流增广
2. 检查这次增广使用了哪个厨师的位置节点（比如厨师 $j$ 的第 $k$ 个位置）
3. 为厨师 $j$ 添加第 $k+1$ 个位置节点 $node_{j,k+1}$
   • 菜品 $i$ → $node_{j,k+1}$：容量 $1$，费用 $(k+1) \times t_{i,j}$
   • $node_{j,k+1}$ → 汇点：容量 $1$，费用 $0$
4. 继续增广，直到总流量达到 $p$

---

算法步骤

1. 数据结构

struct Edge {
    int to, next, cap, cost;
};

vector<Edge> edges;
vector<int> head;
int node_cnt; // 当前节点总数

2. 初始化

// 节点分配
int src = 0;                    // 源点
vector<int> dish_node(n+1);     // 菜品节点
for (int i = 1; i <= n; i++) dish_node[i] = i;
int sink;                      // 汇点，动态更新

// 厨师位置节点管理
vector<vector<int>> chef_node(m+1);  // chef_node[j][k] 表示厨师j的第k个位置节点
vector<int> chef_pos(m+1, 0);        // 厨师j当前有多少个位置节点

3. 添加边函数

void add_edge(int u, int v, int cap, int cost) {
    edges.push_back({v, head[u], cap, cost});
    head[u] = edges.size() - 1;
    edges.push_back({u, head[v], 0, -cost});
    head[v] = edges.size() - 1;
}

4. 初始建图

// 源点到菜品
for (int i = 1; i <= n; i++) {
    add_edge(src, dish_node[i], p[i], 0);
}

// 初始厨师位置节点（第1个位置）
sink = n + 1;
for (int j = 1; j <= m; j++) {
    chef_node[j].push_back(++node_cnt);  // 第一个位置节点
    chef_pos[j] = 1;
    
    // 菜品到厨师位置
    for (int i = 1; i <= n; i++) {
        add_edge(dish_node[i], chef_node[j][0], 1, t[i][j]);
    }
    // 厨师位置到汇点
    add_edge(chef_node[j][0], sink, 1, 0);
}
node_cnt++; // 汇点占用一个编号

5. 最小费用最大流（SPFA实现）

pair<int, int> min_cost_max_flow(int s, int t) {
    int flow = 0, cost = 0;
    while (true) {
        // SPFA找最短路
        vector<int> dist(node_cnt, INF);
        vector<int> pre(node_cnt, -1);
        vector<int> inq(node_cnt, 0);
        queue<int> q;
        
        dist[s] = 0;
        q.push(s);
        inq[s] = 1;
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = 0;
            
            for (int i = head[u]; i != -1; i = edges[i].next) {
                Edge &e = edges[i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    pre[e.to] = i;
                    if (!inq[e.to]) {
                        q.push(e.to);
                        inq[e.to] = 1;
                    }
                }
            }
        }
        
        if (dist[t] == INF) break;
        
        // 增广
        int f = INF;
        for (int u = t; u != s; u = edges[pre[u]^1].to) {
            f = min(f, edges[pre[u]].cap);
        }
        
        flow += f;
        cost += f * dist[t];
        
        for (int u = t; u != s; u = edges[pre[u]^1].to) {
            edges[pre[u]].cap -= f;
            edges[pre[u]^1].cap += f;
        }
        
        // 动态加边：检查哪个厨师被使用了
        for (int j = 1; j <= m; j++) {
            // 检查厨师j的所有位置节点
            for (int k = 0; k < chef_pos[j]; k++) {
                int node = chef_node[j][k];
                // 如果这个节点到汇点的反向边有流量，说明被使用了
                // 找到从node到汇点的边
                for (int i = head[node]; i != -1; i = edges[i].next) {
                    if (edges[i].to == sink && edges[i^1].cap > 0) {
                        // 这个位置被使用了，添加下一个位置
                        if (k == chef_pos[j] - 1) { // 使用的是最后一个位置
                            chef_node[j].push_back(++node_cnt);
                            chef_pos[j]++;
                            
                            // 添加菜品到新位置的边
                            for (int i = 1; i <= n; i++) {
                                add_edge(dish_node[i], chef_node[j][k+1], 1, (k+2) * t[i][j]);
                            }
                            // 新位置到汇点
                            add_edge(chef_node[j][k+1], sink, 1, 0);
                        }
                    }
                }
            }
        }
    }
    return {flow, cost};
}

---

完整代码

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int to, next, cap, cost;
};

class MinCostMaxFlow {
private:
    vector<Edge> edges;
    vector<int> head;
    int node_cnt;
    
    void add_edge_internal(int u, int v, int cap, int cost) {
        edges.push_back({v, head[u], cap, cost});
        head[u] = edges.size() - 1;
        edges.push_back({u, head[v], 0, -cost});
        head[v] = edges.size() - 1;
    }
    
public:
    MinCostMaxFlow(int n) {
        node_cnt = n;
        head.resize(n, -1);
    }
    
    void add_edge(int u, int v, int cap, int cost) {
        add_edge_internal(u, v, cap, cost);
    }
    
    pair<int, int> min_cost_max_flow(int s, int t, int total_dishes, 
                                     const vector<vector<int>> &t_mat,
                                     vector<vector<int>> &chef_nodes,
                                     vector<int> &chef_pos) {
        int flow = 0, cost = 0;
        int n = t_mat.size() - 1;      // 菜品种数
        int m = t_mat[0].size() - 1;   // 厨师数
        
        while (flow < total_dishes) {
            // SPFA
            vector<int> dist(node_cnt, INF);
            vector<int> pre(node_cnt, -1);
            vector<bool> inq(node_cnt, false);
            queue<int> q;
            
            dist[s] = 0;
            q.push(s);
            inq[s] = true;
            
            while (!q.empty()) {
                int u = q.front(); q.pop();
                inq[u] = false;
                
                for (int i = head[u]; i != -1; i = edges[i].next) {
                    Edge &e = edges[i];
                    if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                        dist[e.to] = dist[u] + e.cost;
                        pre[e.to] = i;
                        if (!inq[e.to]) {
                            q.push(e.to);
                            inq[e.to] = true;
                        }
                    }
                }
            }
            
            if (dist[t] == INF) break;
            
            // 增广
            int f = INF;
            for (int u = t; u != s; u = edges[pre[u]^1].to) {
                f = min(f, edges[pre[u]].cap);
            }
            
            flow += f;
            cost += f * dist[t];
            
            for (int u = t; u != s; u = edges[pre[u]^1].to) {
                edges[pre[u]].cap -= f;
                edges[pre[u]^1].cap += f;
            }
            
            // 动态加边：检查哪个厨师位置被使用了
            // 注意：我们需要检查所有到汇点的边
            for (int j = 1; j <= m; j++) {
                // 检查厨师j的每个位置节点
                for (int k = 0; k < chef_pos[j]; k++) {
                    int node = chef_nodes[j][k];
                    // 检查从node到汇点的反向边是否有流量
                    for (int i = head[node]; i != -1; i = edges[i].next) {
                        if (edges[i].to == t) {
                            // 找到反向边
                            int rev = i ^ 1;
                            if (edges[rev].cap > 0) {
                                // 这个位置被使用了
                                // 如果是最后一个位置，添加新位置
                                if (k == chef_pos[j] - 1) {
                                    // 添加新节点
                                    chef_nodes[j].push_back(node_cnt++);
                                    chef_pos[j]++;
                                    head.push_back(-1); // 扩展head数组
                                    
                                    int new_node = chef_nodes[j][k+1];
                                    
                                    // 添加菜品到新位置的边
                                    for (int dish = 1; dish <= n; dish++) {
                                        add_edge_internal(dish, new_node, 1, (k+2) * t_mat[dish][j]);
                                    }
                                    // 新位置到汇点
                                    add_edge_internal(new_node, t, 1, 0);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        return {flow, cost};
    }
};

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    
    vector<int> p(n+1);
    int total_dishes = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        total_dishes += p[i];
    }
    
    vector<vector<int>> t(n+1, vector<int>(m+1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &t[i][j]);
        }
    }
    
    // 节点设计：
    // 0: 源点
    // 1..n: 菜品节点
    // n+1..: 厨师位置节点（动态添加）
    // 汇点：最后添加
    
    int src = 0;
    int initial_nodes = n + 2; // 菜品 + 源点 + 初始汇点
    MinCostMaxFlow mcmf(initial_nodes);
    
    // 源点到菜品
    for (int i = 1; i <= n; i++) {
        mcmf.add_edge(src, i, p[i], 0);
    }
    
    // 初始：每个厨师第一个位置
    int sink = n + 1;
    vector<vector<int>> chef_nodes(m+1);
    vector<int> chef_pos(m+1, 0);
    
    for (int j = 1; j <= m; j++) {
        chef_nodes[j].push_back(initial_nodes++);
        chef_pos[j] = 1;
        mcmf.add_edge(chef_nodes[j][0], sink, 1, 0);
        
        // 菜品到厨师位置
        for (int i = 1; i <= n; i++) {
            mcmf.add_edge(i, chef_nodes[j][0], 1, t[i][j]); // k=1
        }
    }
    
    // 运行最小费用最大流
    auto result = mcmf.min_cost_max_flow(src, sink, total_dishes, t, chef_nodes, chef_pos);
    
    printf("%d\n", result.second);
    
    return 0;
}

---

复杂度分析

时间复杂度

• 每次增广：SPFA $O(VE)$
• 总增广次数：$p$ 次（每道菜一次）
• 动态加边：总共添加 $p$ 个厨师位置节点
• 总复杂度：$O(p \cdot VE)$，但实际运行很快，因为每次增广后图只增加少量边

空间复杂度

• 节点数：$n + p + 2$，最多约 900
• 边数：$n \times m \times avg_k$，实际远小于 $n \times m \times p$

---

优化技巧

1. Dijkstra 优化

可以用带势能的 Dijkstra 代替 SPFA，复杂度 $O(E \log V)$。

2. 更精细的动态加边

• 只在实际需要时才添加边，而不是每道菜都添加所有菜品的边
• 可以记录每个厨师的最小可用位置

3. 对于小数据

当 $n$ 和 $m$ 很小时，可以直接建完整图，不需要动态加边。

---

总结

本题的解题关键：

1. 理解费用计算：第 $k$ 道菜的贡献是 $k \times t_{i,j}$
2. 网络流建模：转化为最小费用最大流问题
3. 动态加边优化：避免建完整图，只在需要时添加节点和边
4. 实现细节：正确识别哪个厨师位置被使用，及时添加新位置

这是一道经典的费用流应用题，考察了网络流建模能力和优化技巧。