//求AOE網絡關鍵路徑
#include<stdio.h> 
#include<stdlib.h> 
typedef struct node 
{int adjvex; 
int dut; 
struct node *next; 
}edgenode; 
typedef struct 
{int projectname; 
int id; 
edgenode*link; 
}vexnode; 
void CreateGraphic(vexnode*Graphicmap,int projectnumber,int activenumber) 
{int begin,end,duttem; 
edgenode *p; 
for(int i=0;i<projectnumber;i++) 
{Graphicmap[i].projectname=i; 
Graphicmap[i].id =0; 
Graphicmap[i].link =NULL; 
}   
printf("輸入<vi,vj,dut>\n"); 
printf("1,2,3表示第1節點到第2節點之間的活動用了3個單位時間\n"); 
for(int k=0;k<activenumber;k++)
{scanf("%d,%d,%d",&begin,&end,&duttem); 
p=(edgenode*)malloc(sizeof(edgenode)); 
p->adjvex=end-1; 
p->dut=duttem; 
Graphicmap[end-1].id ++; 
p->next=Graphicmap[begin-1].link ; 
Graphicmap[begin-1].link =p; 
} 
} 
int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int&totaltime) 
{int i,j,k,m=0; 
int front=-1,rear=-1; 
int*topologystack=(int*)malloc(projectnumber*sizeof(int));
int*vl=(int*)malloc(projectnumber*sizeof(int));
int*ve=(int*)malloc(projectnumber*sizeof(int)); 
int*l=(int*)malloc(activenumber*sizeof(int));
int*e=(int*)malloc(activenumber*sizeof(int));
edgenode *p; 
totaltime=0; 
for(i=0;i<projectnumber;i++)ve[i]=0; 
for(i=0;i<projectnumber;i++) 
{if(Graphicmap[i].id==0) 
{topologystack[++rear]=i; 
m++; 
} 
} 
while(front!=rear) 
{front++; 
j=topologystack[front]; 
m++; 
p=Graphicmap[j].link ; 
while(p) 
{k=p->adjvex ; 
Graphicmap[k].id --; 
if(ve[j]+p->dut >ve[k]) 
ve[k]=ve[j]+p->dut ; 
if(Graphicmap[k].id ==0) 
topologystack[++rear]=k; 
p=p->next ; 
} 
} 
if(m<projectnumber) 
{printf("\n本程序所建立的圖有回路\n");
return 0; 
}
totaltime=ve[projectnumber-1]; 
for(i=0;i<projectnumber;i++) 
vl[i]=totaltime; 
for(i=projectnumber-2;i>=0;i--) 
{j=topologystack[i]; 
p=Graphicmap[j].link ; 
while(p) 
{k=p->adjvex ; 
if((vl[k]-p->dut )<vl[j]) 
vl[j]=vl[k]-p->dut ; 
p=p->next ; 
} 
} 
i=0; 
printf("| 起點 | 終點 |   e  |   l  |  l-e |  是否關鍵活動  |\n"); 
for(j=0;j<projectnumber;j++) 
{p=Graphicmap[j].link; 
while(p) 
{k=p->adjvex ; 
e[++i]=ve[j]; 
l[i]=vl[k]-p->dut; 
printf("| %4d | %4d | %4d | %4d | %4d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i]); 
if(l[i]==e[i]) 
printf(" 關鍵活動 |"); 
printf("\n"); 
p=p->next ; 
} 
} 
return 1; 
} 
void seekkeyroot() 
{int projectnumber,activenumber,totaltime=0; 
printf("請輸入這個工程的圖的節點數:"); 
scanf("%d",&projectnumber); 
printf("請輸入這個工程的活動個數:"); 
scanf("%d",&activenumber); 
vexnode* Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode)); 
CreateGraphic(Graphicmap,projectnumber,activenumber); 
SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime); 
printf("整個工程所用的最短時間為：%d個單位時間\n",totaltime); 
} 
void main() 
{seekkeyroot(); 
}