首页 > 代码库 > 关键路径算法（PAT How Long Does It Take (25)）
关键路径算法（PAT How Long Does It Take (25)）
#include<iostream>
#include<stack>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std ;
#define MAXN 100
int map[MAXN][MAXN] ;
int in_cout[MAXN] ;
int e_time[MAXN] ;
int arry[MAXN] ;
int n , e , n_s = 1 ,sum ;
int max(int x , int y){
return x > y ? x : y ;
}
void get_et(){
int i ,j;
stack<int> s ;
for(i = 0 ; i < n ;i++){
if(!in_cout[i])
s.push(i) ;//得到起始点
}
int sep = 0 ;
while(!s.empty()){
int flag = s.top() ; s.pop() ;
arry[sep++] = flag ;
for(i = 0 ; i < n ; i++){
if(map[flag][i]){//将与flag相连的点，入度减去，并判断是否符合条件进入S。
in_cout[i]--;
if(!in_cout[i]) s.push(i) ;
}
}
}
e_time[0] = 0 ;
if(sep < n-1){
n_s = 0 ;
return ;
}
int juci = 0 ;
for(i = 1 ; i < n ; i++){
int t = arry[i] ;
for( j = 0 ; j < n ; j++ ){
if(map[j][t]){
e_time[t] = max(e_time[j]+map[j][t] , e_time[t]) ;
}
juci = max(juci , e_time[t]) ;//记录整个路线上最大的值
}
sum = juci ;
}
}
int main(){
int i , j ,v ,u , w ;
memset(map , 0 ,sizeof(map)) ;
memset(in_cout , 0 ,sizeof(in_cout)) ;
scanf("%d%d" ,&n,&e) ;
for(i = 0 ; i < e ; i++){
scanf("%d%d%d" ,&v,&u,&w) ;
if(w){
map[v][u] = w ;
in_cout[u]++ ;
}
}
get_et() ;
if(n_s)
printf("%d\n" ,sum) ;
else
printf("Impossible\n") ;
return 0 ;
}
关键路径算法（PAT How Long Does It Take (25)）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。