noname.c

关键路径 c语言

#include "stdio.h"
#define PJNUM  100
typedef struct node
{
 int adjvex;
 int dut;
 struct node *next;
}edgenode;
typedef struct
{
 int pjname;
 int id;
 edgenode *link;
}vexnode;
vexnode map[PJNUM];
void AOE(vexnode *map,int pjnum,int actnum)
{
  int begin,end,duttem;
  int i,k;
  edgenode *p;
  for(i=0;i<pjnum;i++)
  {
   map[i].pjname=i;
   map[i].id=0;
   map[i].link=NULL;
  }
  printf("\n intput <vi> <vj> <dut>\n");
    for(k=0;k<actnum;k++)
    {
      printf("\n Di %d zu :",k);
      scanf("%d%d%d",&begin,&end,&duttem);
      p=(edgenode*)malloc(sizeof(edgenode));
      p->adjvex=end-1;
      p->dut=duttem;
      map[end-1].id++;
      p->next=map[begin-1].link;
      map[begin-1].link=p;
    }
}
int SearchMapPath(vexnode *map,int pjnum,int actnum,int *totaltime)
{
 int i,j,k,m=0;
 int front=-1,rear=-1;
 int *topo=(int*)malloc(pjnum*sizeof(int));
 int *vl=(int*)malloc(pjnum*sizeof(int));
 int *ve=(int*)malloc(pjnum*sizeof(int));
 int *l=(int*)malloc(actnum*sizeof(int));
 int *e=(int*)malloc(actnum*sizeof(int));
edgenode *p;
totaltime=0;
for(i=0;i<pjnum;i++)
   ve[i]=0;
for(i=0;i<pjnum;i++)
{
  if (map[i].id==0)
  {
    topo[++rear]=i;
    m++;
  }
}
while(front!=rear)
{
 front++;
 j=topo[front];
   m++;
 p=map[j].link;
 while(p)
 {
   k=p->adjvex;
   map[k].id--;
   if((ve[j]+p->dut)>ve[k])
      ve[k]=ve[j]+p->dut;
   if(map[k].id==0)
      topo[++rear]=k;
   p=p->next;
 }
}
if(m<pjnum)
{
   printf("\nthe map has a circle!!!\n jiang exit the cheng xu!!\n");
     return 0;
}
totaltime=ve[pjnum-1];
for(i=0;i<pjnum;i++)
    vl[i]=totaltime;
for(i=pjnum-2;i>=0;i--)
{
     j=topo[i];
     p=map[j].link;
   while(p!=NULL)
   {
     k=p->adjvex;
     if((vl[k]-p->dut)<vl[j])
  vl[j]=vl[k]-p->dut;
     p=p->next;
   }
}
i=0;
printf("start end zuizaot zuichit chazhi  \n");
for(j=0;j<pjnum;j++)
{
   p=map[j].link;
   while(p!=NULL)
   {
      k=p->adjvex;
      e[++i]=ve[j];
      l[i]=vl[k]-p->dut;
      printf("\n%d%6d%6d%6d%8d",map[j].pjname+1,map[k].pjname+1,e[i],l[i],l[i]-e[i]);
      if(l[i]==e[i])
  printf(" guan jian huo dong");
      p=p->next;
   }
}
  printf("\n*******************gong qi:   %d \n ",totaltime);
}

int main()
{
  int i;
  int pjnum,actnum,totaltime=0;
  char ch;
  for(;;)
  {
   do
    {
    system("cls");
     printf("\n           Welcome to guanjian lujing suanfa!!!\n");
     for(i=0;i<80;i++)
  printf("*");
     printf("%s","\n   1   input the node and qiuchu guanjian lujing\n");
     printf("%s","\n   2   tuichu chengxu \n\n");
     for(i=0;i<80;i++)
  printf("*");
     printf("%s","please input your xuanzhe:");
     scanf("%c",&ch);
    }while(ch!='1'&&ch!='2');
   if(ch=='1')
    {
      printf("please input the number of node:");
         scanf("%d",&pjnum);
      printf("\nplease input the numberof active:");
         scanf("%d",&actnum);
      AOE(map,pjnum,actnum);
      SearchMapPath(map,pjnum,actnum,totaltime);
      system("pause");
    }
   else if(ch=='2')
       {
          return 1;
       }
}

}