关键路径(AOE)

前面这段话是引用别人的，后面代码是自己写的，有待完善：

 

求关键路径的关键如下：

1、每个顶点所代表的事件的最早和最迟发生时间

2、每条弧所代表的活动的最早和最迟开始时间

事件的最早发生时间：ve[源点]=0，ve[k]=MAX{ve[j]+dut(<j,k>)}，即在k前面的事件的最早发生时间加上那些事件到k所需要的时间所得的值中取最大值。

事件的最迟发生时间：vl[汇点]=ve[汇点]，vl[j]=MIN{vl[k]-dut(<j,k>)}，即在j后面的事件的最迟发生时间减去j到那些事件所需的时间所得的值中取最小值。

活动的最早开始时间：ee[i]=ve[j]，即该项活动最早开始时间与该项活动的开始事件的最早时间相同

活动的最迟开始时间：el[i]=vl[k]-dut(<j,k>)，即活动的最迟开始时间等于该项活动的结束事件的最迟发生时间减去该项活动持续的时间。

 

测试用例图示：

代码：

#include <iostream>
#include <cstdio>
using namespace std;

int n;          //顶点数 
int m;          //有向边数 
int w[1001][1001];         //有向图权值 
int indegree[1001];            //顶点入度 

int queue[1001];               //已经找到的拓扑序列：从队首到队尾按照拓扑排序 
int l=0;       //逐个将已经找到的拓扑序列中的顶点queue[l]从有向图中删除掉（包括删除它的出边） 
int r=0;       //拓扑子序列长度 :queue[r]为目前找到的拓扑子序列最后一个顶点 

int ve[1001];                //顶点（事件） 的最早时间 
int pi[1001];  //关键路径的前驱图 
int path[1001];                    

/*
  测试数据: (见图 )
            5 6
            1 3 3
            1 2 4
            2 5 3
            3 4 1
            3 5 2
            4 5 3
*/
void init(){
     int i,a,b,c;
     scanf("%d%d",&n,&m);
     for(i=1;i<=m;i++){
         scanf("%d%d%d",&a,&b,&c);
         w[a][b]=c;
         indegree[b]++;
     }
}

/* 顶点i加入拓扑序列 */
inline void enQueue(int i){
       queue[++r]=i;
}
/* 从有向图中删除顶点v  -->  拓扑排序时逐个删除找到拓扑序的顶点v */
inline void del(int v){
       int i;
       for(i=1;i<=n;i++){
           if(w[v][i]){
               indegree[i]--;
               if(!indegree[i])
                   enQueue(i);
           }
       }
}

/* 拓扑排序*/
void topo(){
     //找拓扑序列的第一个顶点（不唯一） 
     for(int i=1;i<=n;i++){
         if(!indegree[i])
             enQueue(i);
     }
     
     while(r<n){
         l++;
         del(queue[l]);
     }
}

/*
  关键路径由杜邦公司发明，决定整个项目的工期。
  AOE网：用顶点表示事件，用弧表示活动，弧的权表示活动的持续时间。 对于一个工程，有一个顶点表示整个工程开始（事件），另一个顶点表示这个工程结束（事件） 
*/
void criticalPath(){
     int i,j;
     memset(ve,0,sizeof(ve));
     /*
       ve[i]=max{v[j]+w[j][i]|w[j][i]>0}
     */ 
     for(i=1;i<=n;i++){                 //queue[i]: queue[1~n]按拓扑序排列的顶点 
         for(j=1;j<=n;j++){        //i的所有直接前驱 
             if ( (w[j][queue[i]]>0) && (ve[j]+w[j][queue[i]]>ve[queue[i]]) ){
                 ve[queue[i]]=ve[j]+w[j][queue[i]];
                 pi[queue[i]]=j;
             }
         }
     }
}

/*打印以i为终点的关键路径（包括i）*/
void print(int i){
     if(i==1){
         cout<<1;
         return;
     }
     print(pi[i]);
     cout<<"-->"<<i;
}

void print(){
     printf("总工期: %d\n",ve[n]); 
     
     printf("一条关键路径: "); 
     print(n);
}

int main(){
    init();
    topo();
    criticalPath();
    print();
    
    system("pause");
    return 0;
}