拓扑排序（二）关键路径

P1113 [USACO02FEB] 杂务 - 洛谷
接上讲，在做这道题的时候，是否遇到困难了？因为不仅仅是拓扑排序，还要求出最早完成时间。这引出了我们今天要讨论的另一个话题：关键路径。

关键路径就是项目最短完成时间所经过的路径。

求解关键路径需要准备 2 个数组：

1. ve[i], 记录从起点出发，最早什么时间能到达第 i 项任务。
2. vl[i], 不延迟的情况下，最晚什么时间必须到达任务 i。

其中，如果只求最短完成时间，例如开始那道题，ve 数组就足够了；如果还要求关键路径到达经过哪些节点，那就一定需要 vl 数组了。

我们还是用一道例题来说明这两个数组的使用方法。设我们有 6 个点：

0→1 (3)
0→2 (2)
1→3 (2)
2→3 (1)
3→4 (4)
4→5 (2)

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

struct Edge {
    int to, w;
};

int main() {
    int n = 6;
    vector<vector<Edge>> adj(n);
    
    // 建图
    auto add = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
    };
    
    add(0,1,3);
    add(0,2,2);
    add(1,3,2);
    add(2,3,1);
    add(3,4,4);
    add(4,5,2);
    
    // ---------- 1. 拓扑排序 ----------
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++) {
        for (auto e : adj[u]) {
            indeg[e.to]++;
        }
    }
    
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (indeg[i] == 0) q.push(i);
    }
    
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (auto e : adj[u]) {
            if (--indeg[e.to] == 0) {
                q.push(e.to);
            }
        }
    }
    
    // ---------- 2. 求 ve ----------
    vector<int> ve(n, 0);
    
    for (int u : topo) {
        for (auto e : adj[u]) {
            ve[e.to] = max(ve[e.to], ve[u] + e.w);
        }
    }
    
    // 项目最短时间
    int maxTime = ve[topo.back()];
    
    // ---------- 3. 求 vl ----------
    vector<int> vl(n, maxTime);
    
    for (int i = n - 1; i >= 0; i--) {
        int u = topo[i];
        for (auto e : adj[u]) {
            vl[u] = min(vl[u], vl[e.to] - e.w);
        }
    }
    
    // ---------- 4. 输出关键路径 ----------
    cout << "Critical edges:\n";
    for (int u = 0; u < n; u++) {
        for (auto e : adj[u]) {
            if (ve[u] == vl[e.to] - e.w) {
                cout << u << " -> " << e.to << "\n";
            }
        }
    }
    
    cout << "Min project time = " << maxTime << endl;
    
    return 0;
}

我们现在该做的就是读懂这段代码，在参照这段代码解决开头的那道题目。