预备知识

　　1、由于整个工程只有一个开始点，一个结束点，故在正常情况下（无环），网中只有一个入度为0的点和一个出度为0的点。

　　2、与AOV网不同，AOE网中有些活动可以并行的进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫做关键路径。

　　扩展阅读

　　由于在严蔚敏的《数据结构》中有详细的证明过程，我就不赘述啦，这里我只给出具体实现的代码。

　　[cpp]

　　#include <iostream>

　　#include <cstdlib>

　　#include <cstdio>

　　#include <cstring>

　　#include <queue>

　　#include <stack>

　　using namespace std;

　　const int MAXN = 1010;

　　const int MAXM = 10010;

　　struct Edge

　　{

　　int v, w;

　　int id;

　　int next;

　　}edge[MAXM];

　　int n, m;

　　int cnt;

　　int first[MAXN], topo[MAXN];

　　int ind[MAXN], outd[MAXN];

　　int tot;

　　int Ee[MAXN], El[MAXN], E[MAXN], L[MAXN];

　　/*Ee表示事件最早可能发生时间，El表示事件最迟允许发生时间*/

　　/*E表示活动最早可能发生时间，L表示活动最迟允许发生时间*/

　　void init()

　　{

　　cnt = 0;

　　tot = 0;

　　memset(first, -1, sizeof(first));

　　memset(ind, 0, sizeof(ind));

　　memset(outd, 0, sizeof(outd));

　　memset(Ee, 0, sizeof(Ee));

　　memset(E, 0, sizeof(E));

　　memset(L, 0, sizeof(L));

　　}

　　void read_graph(int u, int v, int w, int id)

　　{

　　edge[cnt].v = v, edge[cnt].w = w, edge[cnt].id = id;

　　edge[cnt].next = first[u], first[u] = cnt++;

　　}

　　void toposort() //拓扑排序

　　{

　　queue<int> q;

　　for(int i = 0; i < n; i++) if(!ind[i]) q.push(i);

　　while(!q.empty())

　　{

　　int x = q.front(); q.pop();

　　topo[++tot] = x;

　　for(int e = first[x]; e != -1; e = edge[e].next)

　　{

　　int v = edge[e].v, w = edge[e].w;

　　if(--ind[v] == 0) q.push(v);

　　if(Ee[v] < Ee[x] + w) //求出各个顶点Ee值

　　{

　　Ee[v] = Ee[x] + w;

　　}

　　}

　　}

　　}

　　void CriticalPath()

　　{

　　toposort();

　　int top = tot;

　　for(int i = 0; i < n; i++) El[i] = Ee[n-1]; //初始化顶点事件的最迟发生时间

　　while(top) //逆拓扑排序求顶点El的值

　　{

　　int x = topo[top--];

　　for(int e = first[x]; e != -1; e = edge[e].next)

　　{

　　int v = edge[e].v, w = edge[e].w;

　　if(El[x] > El[v] - w)

　　{

　　El[x] = El[v] - w;

　　}

　　}

　　}

　　for(int