先对几个概念做一些浅析
最早发生时间
比如事件a的发生需要先发生b和c
而b和c的时间最大值即为最早发生时间，从实际意义来说
烧水需要10min，扫地需要3min，完成这两个任务你才可以
出去玩，所有的事件应该都是可以同时发生的，则你可以在
烧水的时候去扫地，这样你只需要10min就可以出去玩了。
最晚发生时间
前提：工程a在最早完成的基础上
比如整个工程所需要的最少时间为10天，而事件p需要5天
那么p可以在第5天之前的任何一天开始做，既然是最晚发生
那么就在第五天开始做。
也就是在工程最早完成的前提下，p最晚开始。
活动的最早开始时间
顾名思义，最早开始做就可以
活动的最晚开始时间
因为活动有持续时间，那么他就要在活动完成后的事件p之前
活动持续时间开始，而事件p也是在最晚发生的前提之下。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define MAX_VERTEX_NUM 20 4 #define ERROR 0 5 #define OK 1 6 typedef enum{DG, DN, UDG, UDN} GraphKind; 7 typedef char VertexData; 8 typedef struct ArcNode{ 9 int adjvex; 10 int weight; 11 struct ArcNode *nextarc; 12 //Other 13 }ArcNode; 14 15 16 typedef struct VertexNode{ 17 VertexData data; 18 ArcNode *firstarc; 19 }VertexNode; 20 21 typedef struct{ 22 VertexNode vertex[MAX_VERTEX_NUM]; 23 int vexnum, arcnum; 24 GraphKind kind; 25 }AdjList; 26 27 int ve[MAX_VERTEX_NUM]; 28 int TopoOrder(AdjList G, stack<int> &T){ 29 int count; 30 ArcNode *p; 31 int indegree[MAX_VERTEX_NUM], ve[MAX_VERTEX_NUM]; 32 stack<int> s; 33 FindID(G, indegree); 34 for(int i = 0; i < G.vexnum;i++) 35 if(indegree[i] == 0) 36 s.push(i); 37 count = 0; 38 for(int i = 0; i < G.vexnum; i++) 39 ve[i] = 0; 40 while(!s.empty()){ 41 int j = s.top(); 42 T.push(j); 43 count++; 44 p = G.vertex[j].firstarc; 45 while(p){ 46 int k = p->adjvex; 47 if(--indegree[k] == 0) 48 s.push(k); 49 if(ve[j] + p->weight > ve[k]) 50 ve[k] = ve[j] + p->weight; 51 52 p = p->nextarc; 53 } 54 } 55 if(count < G.vexnum) 56 return ERROR; 57 else 58 return OK; 59 } 60 int CriticalPath(AdjList G){ 61 ArcNode *p; 62 char tag; 63 int vl[MAX_VERTEX_NUM]; 64 stack<int> T; 65 if(!TopoOrder(G, T)) 66 return ERROR; 67 for(int i = 0; i < G.vexnum; i++) 68 vl[i] = ve[G.vexnum - 1]; 69 //j -- k 70 while(!T.empty()){ 71 int j = T.top(); 72 T.pop(); 73 p = G.vertex[j].firstarc; 74 while(p){ 75 int k = p->adjvex; 76 int dut = p>weight; 77 if(vl[k] - dut <vl[j]) 78 vl[j] = vl[k] - dut; 79 p = p->nextarc; 80 } 81 82 for(int j = 0; j < G.vexnum; j++){ 83 p = G.vertex[j].firstarc; 84 while(p){ 85 int k = p->adjvex; 86 int dut = p->weight; 87 int ei = ve[j]; 88 int li = vl[k] - dut; 89 tag = (ei == li) ? '*':' '; 90 printf("%c, %c, %d, %d, %d, %c\n", G.vertex[j].data, G.vertex[k].data, 91 dut, ei, li, tag); 92 p = p->nextarc; 93 94 } 95 } 96 } 97 return OK; 98 }
