关键路径

#include<iostream>
using namespace std;
#define N 100
#define INF 1000
int G[N][N];//记录时间
int wantime[N];//最早发生时间
int zaotime[N];//最晚发生时间
int in[N];// 入度
int out[N];//出度

void make( int n ){

for(int i=1;i<=n;i++){
    
    for(int j=1;j<=n;j++){
        
        G[i][j]=INF;
        e1[i][j]=INF;
    }
    wantime[i]=INF;
    zaotime[i]=0;
}
}
int topsort( int n )
{
int font=0;int  real=0;
int *que;
int k;
que = new int [n+1];
for(int i=1;i<=n;i++){
    if(in[i]==0){
        que[real++]=i;
        zaotime[i]=0;
    }
}
while (font!=real){
    k=que[font++];
   for(int i=2;i<=n;i++){
    if(G[k][i]!=INF){
        if(zaotime[i]<zaotime[i]+G[k][i]){
            zaotime[i]=zaotime[i]+G[k][i];
        }
        in[i]--;
        if(in[i]==0){
            que[real++]=i;
        }
    }
   }
   if(real <n)
    return 0;
   else 
    return 1;
   
}

}
void importway(int n ){
wantime[n]=zaotime[n];
int i;
int *que ;
int real=0;
int font=0;
que=new int [n+1];
for(int i=1;i<=n;i++){
    if(out[i]==0){
        que[real++]=i;
        wantime[i]=zaotime[i];
        
    }
}
while(font!=real){
    int k=que[font++];
    for(int i=1;i<=n;i++){
        if(G[i][k]!=INF){
            if(wantime[i]>=wantime[k]-G[i][k]){
               wantime[i]>=wantime[k]-G[i][k];
               e1[i][k]=wantime[k]-G[i][k]-zaotime[i]; 
            }
            out[i]--;
            if(out[i]==0){
                que[real++]=i;
            }
        }
    }
    
    
}



}

int main(){

int number;
int edge;
int weight,node1,node2;
cin>>number>>edge;
make(number);
for(int i=1;i<=edge;i++){
  cin>>node1>>node2>>weight;
  G[node1][node2]=weight;
  in[node2]++;
  out[node1]++;
}

if(topsort(number)==0)
return 0;
importway(number);
for(int i=1;i<=numer;i++){
    for(int j=1;j<=number;j++){
       if(e1[i][j]==0)
        cout<<i<< ''<<j<<endl;
    }
}
    


return 0;
}

使用出度以及入度记录节点，进而求最早最晚发生时间。