尽管是用C++编译的，但程序中没有应用什么C++特性，应该算是C语言编写吧。
工程上常常用一个有向无环图来代表一个项目（如下图）。
以节点表示某个事件，以边表示活动，边上的数字表示活动的持续时间。在工程分析上，常常需要找到一条“关键路径”，即此路径直接决定项目的持续时间。
二、算法描述
为求出关键路径，首先要明确以下几个概念：
c1.节点的最早可能开始时间ev
c2.节点的最迟允许开始时间lv
c3.活动（即边）的最早可能开始时间ee
c4.活动的最迟允许开始时间le
c1: ev比较容易理解，设起点的最早开始时间为0，下一个节点的ev就是上一个节点的ev加上边的持续时间；若存在多条路径到达同一节点的情况，则取最大值为该点的ev（因为只有前面所有活动全部完成后该点才能启动）
c2: lv则要采用倒推的方式，如果已知终点的ev为T，则与终点直接相连节点的lv＝T－边的持续时间；如果存在多条路径，ev取最小值。
c3: 边的ee等于其起点的ev
c4：边的le等于其终点的lv减去边的持续时间
算法书上指出：对于图中某条边，如果满足 ev＝lv，则此边为关键路径（的组成部分）
三、算法实现
3.1输入描述
第一行输入图的顶点个数n 和边数m，
第二行开始是边的信息，每条边的数据占一行，格式为：s e t（即表示从顶点s 到顶点e 的一条权值为t的边）顶点编号从0开始！（为了编程方便）
对于上面的图，可以写为：
9 11
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
3.2 输出描述
The Critical Path:
a1:0->1a4:1->4
a8:4->7
a7:4->6
a10:6->8
a11:7->8
其中，aN中n表示边的编号，对应于输入的顺序
3.3 程序实现
/*
数据输入时采用如下的格式：
首先输入顶点个数n 和边数m，
然后输入每条边，每条边的数据占一行，格式为：s e t;表示从顶点s 到顶点e 的一条权值为t的边
顶点编号从0开始！（为了编程方便）
2016.7.22 by PosPro
详见：http://blog.csdn.net/pospro
*/
#include <cstdio>
#include <cstring>
#define MAXN 100 //The Max num of Vertex
#define MAXM 200 //The Max num of Edges
using namespace std;
struct ArcNode //保存边的信息
{
int to, dur, no;
//to: next vertex, dur: the duration of the activities; no: the ID of activity
struct ArcNode *next;
};
//全局变量！
int n,m; //the number of Vertex and Edge，
ArcNode* outEdge[MAXN]; //记录每个顶点对应的出边表
ArcNode* inEdge[MAXN]; //记录每个顶点对应的入边表
int outOrd[MAXN]; //每个顶点的出度
int inOrd[MAXN]; //每个顶点的入度
int ev[MAXN]; //Earliest start time for Vertex
int lv[MAXN]; //Latest start time for Vertex
int ee[MAXM]; //MAXM!! Earliest start time for Edge
int le[MAXM]; //Latest start time for Edge!!
void CriticalPath()
{
int i; //循环变量
int tmp,nxt; //临时变量
int top=-1; //top指示栈顶的位置；-1表示栈空，正整数表示下一个入度（或出度）为零的点的位置
ArcNode* tpNode;
for(i=0;i<n;i++) //扫描inOrd；把所有入度为0的点入栈（一个虚拟的栈，以top表示下一个数据的位置）
{
if(inOrd[i]==0)
{
inOrd[i]=top; //因为inOrd为0，失去了意义，所以正好可以以此来保存栈中下一个元素的位置
top=i; //以这种类似于堆栈的方式，保存所有入度为0的点
}
}
//可以明确的是，如果不存在环的话，必然每个顶点都会遍历一次，所以这里可以做一个循环
//如果循环结束前，入度为0的点就用尽的话，必然是有环的
for(i=0;i<n;i++)
{
if(-1==top)
{
printf("Cycle Detected!!\n");
return;
}
else
{
tmp=top; //tmp记录当前需要处理的顶点号，即入度为0的点
top=inOrd[top];//top中保存下一个入度为0的元素位置
tpNode=outEdge[tmp];//取出入度为零点的出边链表
while(tpNode!=NULL)
{
nxt=tpNode->to;
inOrd[nxt]--; //从该点出发的所有终点的入度减1
if(0==inOrd[nxt]) //若出现新的入度为零的点，则入栈
{
inOrd[nxt]=top;
top=nxt;
}
//其它的都是套路（实现拓扑排序的套路），下面这两句才是为求关键路径而生的
//下一个点的最早开始时间，必然是上一个点的最早开始时间＋活动持续时间
//如果到达该点有多个路径，最早开始时间必然是个值中的最大值！（因为有一条路径未完成，该点就不能启动）
//第一个起点的ev值，在初始化时就被设为0了
if(ev[nxt]<tpNode->dur+ev[tmp])
ev[nxt]=tpNode->dur+ev[tmp];
tpNode=tpNode->next;
}
}
}
//以入度邻接表，再来一遍
int maxtime=0;
for(i=0;i<n;i++) //找出工程所需时间（总时间）
if(ev[i]>maxtime)
maxtime=ev[i];
top=-1; //重新设栈顶
for(i=0; i<n; i++)
{
lv[i]=maxtime; //先将所有节点的最迟开始时间都设为最后时间
if(0==outOrd[i]) //依然是设栈，解释见上面雷同程序
{
outOrd[i]=top;
top=i;
}
}
for(i=0; i<n; i++)
{
if(-1==top)
{
printf("Back Cycle Detected.\n");
return;
}
else
{
tmp=top; //这些都是套路了，解释见上
top=outOrd[top];
tpNode=inEdge[tmp];
while(tpNode!=NULL)
{
nxt=tpNode->to; //其实是找上一个点
outOrd[nxt]--;
if(0==outOrd[nxt])
{
outOrd[nxt]=top;
top=nxt;
}
//下面两句计算最迟开始时间
//只要有一条路径决定它在更早的时间开始，就得更早开始，所以取各路径最小值
if(lv[nxt]>(lv[tmp]-tpNode->dur))
lv[nxt]=(lv[tmp]-tpNode->dur);
tpNode=tpNode->next;
}
}
}
//上面计算的都是节点（！）的最早和最迟开始时间，下面需要计算边的
//若边（活动）的最早开始＝＝最迟开始时间，则该边为关键路径
printf("The Critical Path:\n");
for(i=0; i<n; i++) //通过出边表，遍历每条边！！（但必须从顶点入手，理出每个顶点的出边表）
{
tpNode=outEdge[i];
while(tpNode!=NULL)
{
tmp=tpNode->no; //tmp此时保存边的编号！！
nxt=tpNode->to;
ee[tmp]=ev[i];//边的最早开始时间就是其起点的最早开始时间
le[tmp]=lv[nxt]-tpNode->dur; //边的最迟开始时间，是其终点的最迟开始时间减去边的持续时间
if(ee[tmp]==le[tmp])
printf("a%d:%d->%d\n",tmp,i,nxt);
tpNode=tpNode->next;
}
}
}
int main()
{
int i;
int s,e,t; //start point; end point; time needed
ArcNode* newNode; //只定义，未初始化
memset(outEdge, NULL, sizeof(outEdge));
memset(inEdge, NULL, sizeof(inEdge));
memset(outOrd, 0, sizeof(outOrd)); //必须初始化为0
memset(inOrd,0, sizeof(inOrd));
memset(ev,0,sizeof(ev));
memset(lv,0,sizeof(lv));
memset(ee,0,sizeof(ee));
memset(le,0,sizeof(le));
scanf("%d%d",&n,&m); //读入输入数据，共计n个顶点和m条边
for(i=0;i<m;i++)
{
scanf("%d%d%d",&s,&e,&t);
//构建出边表
outOrd[s]++; //起点的出度增加
newNode=new ArcNode; //初始化赋值
newNode->to=e;
newNode->no=i+1; //这个是边的编号，第一条读入的边作为1号边
newNode->dur=t;
newNode->next=NULL; //NULL需要大写！
if(outEdge[s]==NULL) //没有之前的出边，则直接赋值；若有，则需像挂接火车车厢一样，挂接链表
outEdge[s]=newNode;
else
{
newNode->next=outEdge[s];
outEdge[s]=newNode;
}
//构建入边表
inOrd[e]++;
newNode=new ArcNode; // 必须重新赋值
newNode->to=s;
newNode->no=i+1;
newNode->dur=t;
newNode->next=NULL;
if(inEdge[e]==NULL)
inEdge[e]=newNode;
else
{
newNode->next=inEdge[e];
inEdge[e]=newNode;
}
}
//一次性获得全部输入后，执行程序的核心部分——找出关键路径
CriticalPath();
//Release the Memory
for(i=0;i<n;i++)
{
while(outEdge[i]!=NULL)
{
newNode=outEdge[i]->next; //newNode不是新节点，只是借用一下其名字
delete outEdge[i];
outEdge[i]=newNode;
}
while(inEdge[i]!=NULL)
{
newNode=inEdge[i]->next;
delete inEdge[i];
inEdge[i]=newNode;
}
}
return 0;
}