.求关键路径
  　设有一个工程网络如下图表示(无环路的有向图)：

  　其中，顶点表示活动，①表示工程开始，⑤表示工程结束(可变，用n表示)，边上的数字表示活动延续的时间。



  如上图中，活动①开始5天后活动②才能开始工作，而活动③则要等①、②完成之后才能开始，即最早也要7天后才能工作。

  　在工程网络中，延续时间最长的路径称为关键路径。上图中的关键路径为：①—②—③—④—⑤共18天完成。

　关键路径的算法如下：

1.数据结构：

　r[1..n，1..n]of integer；　　　表示活动的延续时间，若无连线，则用-1表示；

  　eet[1..n]　　　　　　　　　　　表示活动最早可以开始的时间

  　et[1..n]　　　　　　　　　　 　表示活动最迟应该开始的时间

     关键路径通过点j，具有如下的性质：eet[j]=et[j]

2.约定：

  　结点的排列已经过拓扑排序，即序号前面的结点会影响序号后面结点的活动。

程序清单：

program gao7_6；
　var i，j，n，max，min，w，x，y：integer；
　　　r：array[1..20，1..20]　of integer；
　　　eet，et：array[1..20]　of integer；
　begin
　　readln(n)
　　for i:=1 to n do
　　　for j:=1 to n do
　　　　r[i，j]:=-1；
　　readln(x，y，w)；{输入从活动x到活动y的延续时间，以0为结束}
　while x<>0 do
　　　begin
　　　　r[x，y]:=w；　①　
　　　end；
　　eet[1]：=0；{认为工程从0天开始}
　　for i：=2 to n do
　　　begin
　　　　max:=0；
　　　　for j:=1 to n do
　　　　　if r[j，i]<>-1 then
　　　　　　　if　②　then max:=r[j，i]+eet[j]；
　　　　eet[i]:=max；
　　　end；
　　　　③　
　　　for i：=n-1 downto 1 do
　　　　begin
　　　　　min：=10000；
　　　　　for j：=1 to n do
　　　　　　if r[i，j]<>-1 then
　　　　　　　　if　④　then min：=et[j] - r[i，j]；
　　　　　　　et[i]：=min；
　　　　　　end；
　　　　writeln(eet[n])；
　　　　for i：=1 to n -1 do
　　　　　if　⑤　then write(i，'→')；
　　write(n)；readln
end.