关键路径

以下面的 AOE 网为例。

边表示活动，顶点表示事件。规定：

• 进入某顶点的活动都结束时，该顶点对应的事件发生。
• 顶点对应的事件发生后，从它出去的活动才开始。

关键路径：从起点（源点） 到终点（汇点） 的最长路径的长度。可能有多条。

求法

递推关系 1

事件 的最早发生时间记为 。，且有递推关系

这是按拓扑顺序的递推关系。实际在写代码时，一边 拓扑排序 一边计算递推值。

例子

因为要等所有进入该顶点的活动都结束，所以取最大值。

递推关系 2

在不推迟的情况下，事件 的最迟发生时间记为 。，且有递推关系

这是按拓扑逆序的递推关系。实际在写代码时，根据 拓扑排序 结果倒过来递推。

例子

因为是在不推迟的情况下，所以

• 最迟发生时间等于最早发生时间，即 。
• 算时间时取最小值，尽可能早地让事件发生。

判断关键路径中的活动

如果活动 由 表示，则

• 的最早发生时间记为 。

• 在不推迟的情况下， 的最迟发生时间记为 。

• 满足 的 ，即为关键路径中的活动。

考虑到关键路径可能有多条，在算总长度时，不能简单地把所有满足条件的 全加起来。

代码实现

代码中， 是源点， 是汇点。

int N;                           // 顶点数量
vector<pair<int, int>> G[MAX_N]; // 邻接表，first=顶点, second=权值
int in[MAX_N];                   // 存储每个顶点的入度
int ve[MAX_N], vl[MAX_N];        // ve 和 vl

bool critical_path(vector<int>& ans)
{
    // 把 ve 都初始化为 0
    for (int i = 0; i < N; i++)
    {
        ve[i] = 0;
    }

    // 记录拓扑排序的结果
    stack<int> s;

    // 拓扑排序
    queue<int> q;
    for (int i = 0; i < N; i++)
    {
        if (!in[i]) q.push(i);
    }
    while (q.size())
    {
        int v = q.front(); q.pop();
        s.push(v);

        for (pair<int, int>& adj : G[v])
        {
            if (--in[adj.first] == 0) q.push(adj.first);

            // 递推 ve
            ve[adj.first] = max(ve[adj.first], ve[v] + adj.second);
        }
    }

    // 有环
    if (s.size() != N)
    {
        return false;
    }

    // 把 vl 都初始化为最大值 ve(n-1)
    for (int i = 0; i < N; i++)
    {
        vl[i] = ve[t.top()];
    }

    while (s.size())
    {
        int v = s.top(); s.pop();

        for (pair<int, int>& adj : G[v])
        {
            // 按拓扑逆序递推 vl
            vl[v] = min(vl[v], vl[adj.first] - adj.second);
        }
    }

    // 找出一条关键路径
    int v = 0;
    ans.push_back(0);
    while (v != N - 1)
    {
        for (pair<int, int>& adj : G[v])
        {
            int ee = ve[v];
            int el = vl[adj.first] - adj.second;
            if (ee == el)
            {
                v = adj.first;
                ans.push_back(v);
                break;
            }
        }
    }
    return true;
}