关键路径_AOE_基于邻接表

//AOE_求关键路径_基于邻接表

//首先用正向邻接表求出每个活动的最早发生时间
//   用逆向邻接表求出每个活动的最迟发生时间
//再两者对应相减，为0即为活动的关键活动
//
//大纲：删除无前继结点的顶点  
//  
//输入：  
//   先确定顶点数和边数  
//   分为头结点和值结点，头结点含有count，用于计数这个结点当前含有的前继  
//
//求出每个活动的最早发生时间的时候，当前路径小于新的时候，更换
//求出每个活动的最迟发生时间的时候，当前路径大于新的时候，更换
//
//  使用栈记录count为0的结点，栈空时结束  
//  当count--后为0，说明这个结点的前继处理完了，把这个结点放入栈里  

//(由于关键路径既是最长路径，所以可以增加代码，保留合理的前继就可以知道路上的关键活动了)

/*
9 11
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
035214768
875364210
earliest0 -latest0  0 - 0 = 0
earliest1 -latest1  6 - 6 = 0
earliest2 -latest2  4 - 6 = -2
earliest3 -latest3  5 - 8 = -3
earliest4 -latest4  7 - 7 = 0
earliest5 -latest5  7 - 10 = -3
earliest6 -latest6  16 - 16 = 0
earliest7 -latest7  14 - 14 = 0
earliest8 -latest8  18 - 18 = 0
Press any key to continue
 
  */
  
#include <iostream>  
using namespace std;  
   
 typedef struct zhinode *zhinode_pointer;  
 struct zhinode值结点  
 {  
    zhinode(){link=NULL;}  
    int var;  
    int length;
    zhinode_pointer link;  
 };  
struct heapnode///头结点  
{  
    heapnode(){count=0;link=NULL;}  
    int count;  
    zhinode_pointer link;  
};  
void draw(struct heapnode *&,struct heapnode *&);//绘图     
void insert(struct heapnode *heap,int a,int b,int c);//连接值结点  
void deal_first(struct heapnode *,int *&);//
void deal_second(struct heapnode *,int *&,int *&);//
void out(int *a,int *b);
int v,edge;  
  
  
int main(int argc, char const *argv[])  
{  
     struct heapnode *first,*second;
     draw(first,second);  

    int *earliest;
    deal_first(first,earliest);
    cout<<endl;

    int *latest;
    deal_second(second,latest,earliest);
     cout<<endl;

    out(earliest,latest);
    return 0;  
}  
  
void draw(struct heapnode * &first,struct heapnode * &second)//绘图      
{      
  int i;  
  int spot1,spot2,len;      
  cin>>v>>edge;///输入点数目  
  
 first=new struct heapnode[v];  
 second=new struct heapnode[v];   
  for (i = 0; i < edge; ++i)  
  {  
    cin>>spot1>>spot2>>len;  
    insert(first,spot1,spot2,len);  
   insert(second,spot2,spot1,len);
  } 
}  
void insert(struct heapnode *heap,int a,int b,int c)  
{  
    heap[b].count++;//b的前继加1  
    zhinode_pointer ok=new struct zhinode;//增加值结点  
    if(ok==NULL)cerr<<"申请失败";  
    ok->var=b;
    ok->length=c;//给值结点赋值  
  
    zhinode_pointer item=heap[a].link;  
      
    if(item==NULL)heap[a].link=ok;//无链时  
    else{//有链时  
        zhinode_pointer dangqian=item;  
        while(item)  
        {  
            dangqian=item;  
            item=item->link;  
        }  
        dangqian->link=ok;  
    }  
     
}  
///-------------------------------------------------------------///      
void deal_first(struct heapnode *heap,int *&earliest)//
{  
   int* zhan=new int[v];  
   int zhan_top=0;  
   int temp;//记录当前正在使用的头结点的位置
  earliest=new int[v];
   for (int i = 0; i < v; ++i)  
   {
        if(heap[i].count==0)zhan[zhan_top++]=i;//count为0时。进栈；
        earliest[i]=0;  
   }
    if(zhan_top==0 || zhan_top >=2)cerr<<"error,没有头结点或不只有一个头结点";  
  
  
    zhinode_pointer will_free;  
    zhinode_pointer item;  
    while(zhan_top!=0)//有结点在栈里 
    {  
        will_free=heap[ zhan[--zhan_top] ].link;//要删除的值结点  
        temp=zhan[zhan_top];
        cout<<temp;//输出某个工程  
        while(will_free != NULL)//要删除的开始结点不为空  
        {  
        	if ((earliest[temp] + will_free->length) > earliest[will_free->var])//路径更长，路径长度更换，可以增加代码用于记录合理的前继
     			earliest[will_free->var] = earliest[temp] + will_free->length;

           item=will_free->link;//下一个值结点  
          if( !--heap[will_free->var].count )zhan[zhan_top++]=will_free->var;//当count为0时，说明前继处理完了，进栈。  
          delete will_free;//删除值结点  
          will_free=item;  
        }             
  
    }  
   delete zhan;  
}  
void deal_second(struct heapnode *heap,int *&latest,int *&earliest)//
{  
   int* zhan=new int[v];  
   int zhan_top=0;  
   int temp;//记录当前正在使用的头结点的位置
  latest=new int[v];
   for (int i = 0; i < v; ++i)  
   {
        if(heap[i].count==0)zhan[zhan_top++]=i;//count为0时。进栈；
        latest[i]=earliest[v-1];//必须有这句开头啊
   }
    if(zhan_top==0 || zhan_top >=2)cerr<<"error,没有头结点或不只有一个头结点";  
  
    zhinode_pointer will_free;  
    zhinode_pointer item;  
    while(zhan_top!=0)//有结点在栈里 
    {  
        will_free=heap[ zhan[--zhan_top] ].link;//要删除的值结点  
        temp=zhan[zhan_top];
        cout<<temp;//输出某个工程  
        while(will_free != NULL)//要删除的开始结点不为空  
        {  
        	if ((latest[temp] - will_free->length) < latest[will_free->var])//路径更长，路径长度更换，可以增加代码用于记录合理的前继
     			 latest[will_free->var] = latest[temp] - will_free->length;

        item=will_free->link;//下一个值结点  
        if( !--heap[will_free->var].count )zhan[zhan_top++]=will_free->var;//当count为0时，说明前继处理完了，进栈。  
        delete will_free;//删除值结点  
        will_free=item;  
        }             
  
    }  
   delete zhan;  
}  
void out(int *a,int *b)
{
	for (int i = 0; i < v; ++i)
	{
		cout<<"earliest"<<i<<" -latest"<<i<<"  "<<a[i]<<" - "<<b[i]<<" = "<<a[i]-b[i]<<endl;
	}
}