08-图8 How Long Does It Take

Given the relations of all the activities of a project, you are supposed to find the earliest completion time of the project.

Input Specification:

Each input file contains one test case. Each case starts with a line containing two positive integers

Output Specification:

For each test case, if the scheduling is possible, print in a line its earliest completion time; or simply output "Impossible".

Sample Input 1:

Sample Output 1:

Sample Input 2:

4 5
0 1 1

Sample Output 2:

Impossible

  1 #include<iostream>
  2 #include<malloc.h>
  3 #include<queue>
  4 using namespace std;
  5 
  6 #define INF (100000)
  7 #define MAX 100
  8 //如果采用邻接链表的形式构造图，在每一个顶点中接下存储的边是其相邻的边
  9 typedef struct _Edge{
 10     int Adjv;
 11     int Weight;
 12     
 13 
 14     _Edge *Next;
 15 }Edge,nedge;
 16 
 17 typedef struct _VNode
 18 {
 19     int  NodeName;
 20     
 21     nedge *first_edge;
 22 }VNode;
 23 
 24 typedef struct _Graph{
 25     int Vernum;
 26     int Edgnum;
 27     VNode G[MAX];
 28 
 29 }MGraph;
 30 
 31 MGraph *Graph;
 32 
 33 void link_last(nedge *list, nedge *node)
 34 {  nedge *p=list;
 35 while(p->Next!=NULL)
 36 {
 37     p=p->Next;
 38 }
 39 p->Next=node;
 40 node->Next=NULL;
 41 }
 42 
 43 MGraph *BuildMyGraph(int N,int M)
 44 {     MGraph *pG;
 45     pG=(MGraph*)malloc(sizeof( _Graph));//pG图必须要申请空间
 46 
 47     pG->Vernum=N;pG->Edgnum=M;
 48 
 49     //将点初始化
 50     for(int i=0;i<N;i++)
 51     {
 52         pG->G[i].NodeName=i;
 53     
 54         pG->G[i].first_edge=NULL;
 55     }
 56             //输入数据
 57       int c1,c2,w1,i,j;
 58     Edge *edge;
 59     for(i=0;i<pG->Edgnum;i++)
 60     {
 61         cin>>c1>>c2>>w1;
 62         edge=(Edge*)malloc(sizeof(_Edge));
 63         edge->Adjv=c2;edge->Weight=w1;edge->Next=NULL;
 64         for(j=0;j<pG->Vernum;j++)
 65         {
 66             if(c1==pG->G[j].NodeName)
 67             {
 68                 if(pG->G[j].first_edge==NULL)
 69                 {
 70                     pG->G[j].first_edge=edge;
 71                 }
 72                 else
 73                 {
 74                     link_last(pG->G[j].first_edge,edge);
 75                 }
 76             }
 77         }
 78     }
 79     return pG;
 80 }
 81 int TopSort(int Total)
 82 {int Indegree[MAX],V;int TopOrder[MAX],i;int S[MAX];
 83   queue<int>Q; Edge *E;
 84 
 85   for( i=0;i<Graph->Vernum;i++)
 86          Indegree[i]=0;
 87   //计算其入度，每个顶点的入度
 88   for(i=0;i<Graph->Vernum;i++)
 89   {
 90       E=Graph->G[i].first_edge;
 91       while(E!=NULL)
 92       {
 93           Indegree[E->Adjv]++;
 94           E=E->Next;
 95       
 96       }
 97   }
 98   //找到入度为零的点
 99   for(i=0;i<Graph->Vernum;i++)
100   {
101         if(Indegree[i]==0)
102             {  Q.push(i);
103                 S[i]=0;
104         }
105   }
106   int cnt=0; int temp=0;
107   while(!Q.empty())
108   {
109       V=Q.front();Q.pop();
110       TopOrder[cnt++]=V;
111       for(E=Graph->G[V].first_edge;E;E=E->Next)
112       {
113           temp=E->Weight;
114             //这里只有一句话，只能计算工程完成要多久，如果深入，编写出其
115             //是否有机动组
116           S[E->Adjv]=S[V]+temp> S[E->Adjv]?S[V]+temp:S[E->Adjv];
117           if(--Indegree[E->Adjv]==0)
118                Q.push(E->Adjv);
119       }
120   }
121      if(cnt!=Graph->Vernum)
122            Total=-1;
123      else
124          Total=S[(cnt-1)];
125     return Total;
126 }
127 int main()
128 {
129     int N,M;
130     cin>>N>>M;
131 Graph=BuildMyGraph(N,M);
132     int Total=0;
133     Total =TopSort(Total);
134     if(Total!=-1)
135     {
136         cout<<Total<<endl;
137     }
138     else
139     {
140         cout<<"Impossible"<<endl;
141     }
142     return 0;
143 }