对AOE网求关键路径

2008-10-31 20:20

#include<iostream>
using namespace std;
const int N = 10000000;
const int INC = 20;
int adjmat[10][10] = {{N,6,4,5,N,N,N,N,N},
                      {N,N,N,N,1,N,N,N,N},
                      {N,N,N,N,1,N,N,N,N},
                      {N,N,N,N,N,2,N,N,N},
                      {N,N,N,N,N,N,9,7,N},
                      {N,N,N,N,N,N,N,4,N},
                      {N,N,N,N,N,N,N,N,2},
                      {N,N,N,N,N,N,N,N,4},
                      {N,N,N,N,N,N,N,N,N}};
int vexnum = 9;
class Stack{
      public:
      Stack(){ st = new int[INC]; top = -1; max_size = INC;}
      Stack(int size);
      void Pop(int& i);
      void Push(int i);
      bool IsEmpty(){ return top==-1; }
      private:
      int* st;
      int top;
      int max_size;
};
Stack::Stack(int size){
       st = new int[size+INC];
       top = -1;
       max_size = INC+size;
}
void Stack::Pop(int& i){
     if(IsEmpty()){
        cout<<"Stack Empty!"<<endl;
        system("pause");
        exit(0);
     }
     i = st[top--];
}
void Stack::Push(int i){
     if(top+1>=max_size){
        cout<<"Stack Full!"<<endl;
        system("pause");
        exit(0);
     }
     st[++top] = i;
}
bool TopologicalSort(Stack& uT,int ve[]);
bool CriticalPath();
int main(void){
    if(CriticalPath()) cout<<"No cycle!";
    else cout<<endl<<"Cycle Exist!";
    cout<<endl;
   
    system("pause");
    return 0;
}
bool TopologicalSort(Stack& uT,int ve[]){
     int indeg[10];
     int i,j;
     int count=0;
     Stack st;
     memset(indeg,0,sizeof(indeg));//若ve在这里赋初值会出错或许是因为参数传递。。。。。。

    
     for(i=0;i<vexnum;i++)
         for(j=0;j<vexnum;j++)
             if(adjmat[j][i]<N) indeg[i]++;
    
     for(i=0;i<vexnum;i++)
         if(!indeg[i]) st.Push(i);
    
     while(!st.IsEmpty()){
           st.Pop(i); uT.Push(i);
           count++;
           for(j=0;j<vexnum;j++)
               if(adjmat[i][j]<N){
                  if(--indeg[j]==0) st.Push(j);
                  if(ve[j]<ve[i]+adjmat[i][j]) ve[j] = ve[i] + adjmat[i][j];
              }
     }
       
     if(count<vexnum) return false;
     return true;
}
   
bool CriticalPath(){
     Stack T;
     int ve[10],vl[10];
     int i,j;
     memset(ve,0,sizeof(ve));
    
     if(!TopologicalSort(T,ve)) return false;
     T.Pop(i);
     for(j=0;j<vexnum;j++) vl[j] = ve[i];
    
     while(!T.IsEmpty()){
           for(j=0;j<vexnum;j++)
               if(adjmat[j][i]<N)
                  if(vl[i]-adjmat[j][i]<vl[j])
                     vl[j] = vl[i]-adjmat[j][i];
           T.Pop(i);
     }
    
     for(i=0;i<vexnum;i++)
         for(j=0;j<vexnum;j++)
             if(adjmat[i][j]<N)
                if(ve[i]==vl[j]-adjmat[i][j])
                   cout<<i+1<<"->"<<j+1<<"\t";
     cout<<endl;
    
     return true;
}