基础实验6

基础实验6"/>

基础实验6

基础实验6-2.6 最短工期 (25 分)

拓扑排序，AOE网

#include<stdio.h>
#include<string.h>
const int N=1010;
const int inf=0x3f3f3f;
int map[N][N];
int in[N];   
int early[N];
int ret=0;		   
int n,m,ans=0;
void t1()	
{for(int k=0;k<n;++k){for(int i=0;i<n;i++){if(in[i]==0){ret++;in[i]--;for(int j=0;j<n;j++){if(map[i][j]!=-1){in[j]--;if(early[j]<early[i]+map[i][j])early[j]=early[i]+map[i][j];if(ans<early[j])ans=early[j];}}}}}
}
int main()
{memset(map,-1,sizeof(map)); scanf("%d%d",&n,&m);while(m--){int x,y,z;scanf("%d%d%d",&x,&y,&z);map[x][y]=z;in[y]++;}t1();if(ret==n){printf("%d",ans);} elseprintf("Impossible");return 0;
}