从烹饪流程到拓扑排序：关键路径算法的实战应用

1. 项目概述：当算法遇上厨房

作为一名从OI转行做厨子的程序员，我经常在切菜时思考如何用代码优化烹饪流程。这个GESP5级的烹饪问题完美结合了我的两个职业 passion——算法和料理。题目看似简单：给定n种食材和m个烹饪步骤，计算完成一道菜的最短时间。但其中暗藏了拓扑排序、关键路径等经典算法思想，就像炒菜时火候的掌控一样需要精确计算。

去年辅导学生备考时，我发现这个题目得分率不足40%，主要卡在三个地方：如何建立步骤依赖关系图、如何处理并行操作、怎样优化时间计算。下面我就用米其林后厨的实战经验，带大家拆解这道"美味"的算法题。

2. 核心算法解析

2.1 问题建模技巧

题目通常会给出这样的输入格式：

code复制n=3  // 食材数量
m=4  // 步骤数量
steps = [
  {"name":"切菜", "time":2, "requires":[1]}, 
  {"name":"腌肉", "time":3, "requires":[2]},
  {"name":"炒制", "time":5, "requires":[0,1]},
  {"name":"装盘", "time":1, "requires":[2]}
]

我在实际编码中发现，用邻接表建图时有个易错点：需要同时维护入边和出边关系。建议这样定义数据结构：

cpp复制struct Step {
    string name;
    int time;
    vector<int> next;  // 后继步骤
    vector<int> prev;  // 前驱步骤
    int in_degree = 0;
};

关键技巧：在读取输入时就构建完整的图关系，而不是先存原始数据再处理。这能避免后续拓扑排序时的重复计算。

2.2 拓扑排序实现

标准拓扑排序模板需要配合队列实现：

cpp复制queue<int> q;
for(int i=0; i<m; i++){
    if(steps[i].in_degree == 0){
        q.push(i);
    }
}

while(!q.empty()){
    int cur = q.front();
    q.pop();
    for(int