高级实验室 6-3.5 关键活动（30 分）--拓扑排序

#include <stdio.h> #include <string.h> #define Max 100+1 #define INF 0x3f3f3f3f int G[Max][Max]; int indegree[Max];//记录入度 int outdegree[Max];//记录出度 int ans=0;//完成项目的最短时间 int early[Max];//记录最早完成时间 int late[Max];//记录最迟完成时间 int cnt=0;//记录入度为零的结点个数 int Nv,Ne; void Init() {//图初始化 memset(G,-1,sizeof(G)); memset(early,0,sizeof(early)); memset(late,INF,sizeof(late)); memset(indegree,0,sizeof(indegree)); memset(outdegree,0,sizeof(outdegree)); scanf("%d %d",&Nv,&Ne); int v1,v2,x; int i; for(i=0; i<Ne; i++) { scanf("%d %d %d",&v1,&v2,&x); G[v1][v2]=x; indegree[v2]++; outdegree[v1]++; } } void TopoSortEarly() {//求解最早完成时间 int i,j; while(1) { int flag=0; for(i=1; i<=Nv; i++) { if(!indegree[i]) { cnt++; indegree[i]--; flag=1; for(j=1; j<=Nv; j++) { if(G[i][j]!=-1) { indegree[j]--; if(early[j]<early[i]+G[i][j]) { early[j]=early[i]+G[i][j]; } if(ans<early[j]) { ans=early[j]; } } } } } if(!flag) break; } } void TopoSortLate() {//求解最迟完成时间 int i,j;
//出度为零的结点初始化最迟时间为最早完成时间 for(i=1;i<=Nv;i++) { if(!outdegree[i]) late[i]=ans; } while(1) { int flag=0; for(i=Nv; i>=1; i--) { if(!outdegree[i]) { outdegree[i]--; flag=1; for(j=Nv; j>=1; j--) { if(G[j][i]!=-1) { outdegree[j]--; if(late[i]-G[j][i]<late[j]) late[j]=late[i]-G[j][i]; } } } } if(!flag) break; } } int main() { Init(); int i,j; TopoSortEarly(); if(cnt==Nv) { printf("%d\n",ans); TopoSortLate(); for(i=1; i<=Nv; i++) { if(early[i]==late[i]) { for(j=Nv; j>=1; j--) { if(late[j]==early[j]&&G[i][j]>=0&&late[j]-G[i][j]==early[i]) printf("%d->%d\n",i,j); } } } } else printf("0"); return 0; }