前言在赋权有向图中，顶点表示事件，，有向边表示活动，边上的权值表示该活动持续的时间，则是这样的图
在从源点(入点)到宿点(出点)的所有路径中，路径长度最大的路径称为关键路径。 关键路径上的活动称为关键活动。 对于施工中不重要的活动，可以允许一些延误。 但是，对施工中的重要活动不允许拖延。 为什么这么说，是因为最早的开始时间和最晚的开始时间是一样的。 因为重要活动的拖延会影响整个工程的完成时间。
以这种方式，将转换要求每个活动的最早开始时间和最晚开始时间的关键路径。 然后，通过判断两者是否相等，可以得到关键路径上的重要活动。 那么，如何求出最早的开始时间和最晚的开始时间呢？
对于一个活动，所有前期活动最晚的完成时间就是该活动最早的开始时间。
对于一个活动，所有后排活动的最早开始时间减去该活动所需时间，即为该活动最晚开始时间。
那么如何决定活动的优先顺序呢？ 在这种情况下，需要对拓扑进行排序。
看看例题吧。 请更好地理解。
例题蚂蚁这学期修了“计算机组成原理”这门课。 他知道了命令之间可能有依存关系。 如果两个命令之间的距离(定义为开始时间之差)小于安全距离，这可能会导致错误的结果。 因此，为了确保两个命令之间的距离大于或等于安全距离，必须添加空命令(无用命令)以增加不必要的操作。
你的工作是重新排列指令，使CPU (各指令的执行时间为1ns ) )能够在最短时间内完成所有指令。
输入包含多个组。 每个组：
第一行： n (命令数)、m (命令相关系数) )。
以下m行： x (命令)、y (命令)、z (安全距离) )命令编号0到n-1 ) ) ) ) ) ) 652 )
输出CPU完成所有指令的最短时间
样本输入5 2
1 2 1
3 4 1
样本输出2
一旦该想法将指令的优先依赖关系抽象为有向边，这个实际问题就被转换为判断图上的最长路径的长度，即关键路径的长度。 可以根据拓扑序列逐一求出各活动的最早开始时间，根据拓扑序列的逆序列求出各活动的最晚开始时间。 所有活动中最早开始时间和最晚开始时间相同的活动是关键活动，所有活动中最早开始时间的最大值是关键路径长度。
AOE表示各指令的执行时间为1ns。 也就是说，所有源点的最早开始时间必须初始化为1，而不是普通的0。
(关于最早开始时间的初始化，如果主题没有特别的要求，则将所有节点初始化为0。 对于最大延迟开始时间的初始化，如果没有对主题的特殊请求，则宿点的最大延迟开始时间被初始化为其最早开始时间，其馀节点被初始化为INF。 ）
代码# include iostream # include cstdio # include queue # include vector # include cstring # includeclimitsusingnamespacestd； 常数上限=1001； const int INF=INT_MAX； 结构边缘{ int to； int length； edge(intt，int l ) :to(t )，length(l ) {}； 向量边缘图形[ maxn ]； int earliest[MAXN]； int latest[MAXN]； int inDegree[MAXN]； 语音路径(intn ) { vectorint topology； 队列输入节点； for(intI=0； in； I ) if(indegree[I]==0) ) node.push ) I； earliest[i]=1； 初始化为//11} while (！ node.empty () ) { int u=node.front； topology.push_back(u； node.pop (； for(intI=0； igraph[u].size (； I ) { int v=graph[u][i].to； int l=graph[u][i].length； Earliest[v]=max(Earliest[v]，earliest[u] l )； inDegree[v]--； if(indegree[v]==0) () ) ) ) ) ) ) ) )。
node.push(v); } } for(int i=topology.size()-1;i>=0;i--) { int u=topology[i]; if(graph[u].size()==0) latest[u]=earliest[u]; else latest[u]=INF; for(int j=0;j<graph[u].size();j++) { int v=graph[u][j].to; int l=graph[u][j].length; latest[u]=min(latest[u],latest[v]-l); } }}int main(){ int n,m; while(cin>>n>>m) { memset(graph,0,sizeof(graph)); memset(earliest,0,sizeof(earliest)); memset(latest,0,sizeof(latest)); memset(inDegree,0,sizeof(inDegree)); while(m--) { int from,to,length; cin>>from>>to>>length; graph[from].push_back(Edge(to,length)); inDegree[to]++; } CriticalPath(n); int answer=0; for(int i=0;i<n;i++) answer=max(answer,earliest[i]); cout<<answer<<endl; } return 0;} 例题2 #include<iostream>#include<cstdio>#include<queue>#include<vector>#include<cstring>#include<climits>using namespace std;const int MAXN=1e5+7;const int INF=INT_MAX;const int MOD=1e9+7;vector<int> graph[MAXN];int inDegree[MAXN];long long earliest[MAXN];long long latest[MAXN];long long Time[MAXN];long long CriticalPath(int n){ vector<int> topology; queue<int> node; for(int i=1;i<=n;i++) { if(inDegree[i]==0) { node.push(i); } } long long totalTime=0; while(!node.empty()) { int u=node.front(); topology.push_back(u); node.pop(); for(int i=0;i<graph[u].size();i++) { int v=graph[u][i]; earliest[v]=max(earliest[v],earliest[u]+Time[u]); inDegree[v]--; if(inDegree[v]==0){ node.push(v); totalTime=max(totalTime,earliest[v]+Time[v]); } } } for(int i=topology.size()-1;i>=0;i--) { int u=topology[i]; if(graph[u].size()==0) latest[u]=totalTime-Time[u];//注意不是latest[u]=earliest[u],因为汇点不止一个 else latest[u]=INF; for(int j=0;j<graph[u].size();j++) { int v=graph[u][j]; latest[u]=min(latest[u],latest[v]-Time[u]); } } return totalTime;}int main(){ int n,m; while(cin>>n>>m) { memset(graph,0,sizeof(graph)); memset(earliest,0,sizeof(earliest)); memset(latest,0,sizeof(latest)); memset(inDegree,0,sizeof(inDegree)); memset(Time,0,sizeof(Time)); for(int i=1;i<=n;i++) cin>>Time[i]; while(m--) { int from,to; cin>>from>>to; graph[from].push_back(to); inDegree[to]++; } long long totalTime=CriticalPath(n); long long answer=1; for(int i=1;i<=n;i++) { answer*=latest[i]-earliest[i]+1; } cout<<totalTime<<endl<<answer%MOD<<endl; } return 0;}