我去，一个代码让我写了好几天，一点小错误……
不过这个代码在存储空间上不是最优的，我建立了两个表，一个邻接表一个逆邻接表，然后对邻接表进行top排序，对逆邻接表进行逆top排序
然后遍历每一个边表结点，找和他相连的边，这样把每条边都遍历了一次，同时计算这条边对应事件的最早开始时间和最晚开始时间 ，注意边的标号和这条边两侧的节点的标号在数值上没有关系，也就是说事件a[i]对应的边是<j, k>的话，i和j，k没有关系，
中间犯了几个小错误，找了很久很久……
#include <stack> #include <stdio.h> #include <string.h> #include <malloc.h> #include <iostream> #define M 1005 #define INF 0x3f3f3f using namespace std; typedef struct ArcNode//边表节点 { int adjvex; struct ArcNode *nextarc; int dut; }ArcNode; typedef struct VNode ////表节点 { int data; ArcNode *firstarc; }VNode; VNode adj[M], nadj[M]; ArcNode arc[M];//边表 int e[M], l[M], vl[M], ve[M], n, m, top; int ind[M], outd[M]; //入度，出度， void Init(); void TopSort(); void NTopSort(); void GetArc(int &u, int &v, int &w); void Creat(); void Print2(); void Critical(); int main() { freopen("in.txt", "r", stdin); while(~scanf("%d%d", &n, &m)) { Init(); Creat(); TopSort(); NTopSort(); Print2(); //printf(" The Critical activities are "); Critical(); } return 0; } void Init() { top = 0; memset(ve, 0, sizeof(ve));//最早发生时间初始化为0 memset(vl, INF, sizeof(vl));//最晚发生时间初始化为INF memset(ind, 0, sizeof(ind)); //入度全部初始化为0 memset(outd, 0, sizeof(outd));//出度全部初始化为0 memset(e, 0, sizeof(e)); memset(l, 0, sizeof(l)); } void TopSort() { stack <int> s; for(int i = 0; i < n; i++) if(ind[i] == 0) { s.push(i); } ve[0] = 0; while(!s.empty()) { int i = s.top(), k; s.pop(); ArcNode *p; //printf("i = %d ", i); for(p = adj[i].firstarc; p != NULL; p = p->nextarc) { k = p->adjvex-1; ind[k]--; if(ind[k] == 0) s.push(k); //printf("出发点ve[%d] = %d ", i+1, ve[i]); //printf("指向的点的初始值ve[%d] = %d ", k+1, ve[k]); if(ve[i]+p->dut > ve[k]) ve[k] = ve[i] + p->dut; //printf("更新后指向的点的值ve[%d] = %d********************* ", k+1, ve[k]); } } } void NTopSort() { stack <int> s; for(int i = 0; i < n; i++) if(outd[i] == 0) { s.push(i); } vl[n-1] = ve[n-1]; while(!s.empty()) { int i = s.top(), k; s.pop(); ArcNode *p; for(p = nadj[i].firstarc; p != NULL; p = p->nextarc) { k = p->adjvex-1; outd[k]--; if(outd[k] == 0) s.push(k); //printf("出发点vl[%d] = %d ", i+1, vl[i]); //printf("指向的点的初始值vl[%d] = %d ", k+1, vl[k]); printf("p->dut = %d ", p->dut); if(vl[k] > vl[i] - p->dut) vl[k] = vl[i] - p->dut; //printf("更新后指向的点的值vl[%d] = %d********************* ", k+1, vl[k]); } } } void GetArc(int &u, int &v, int &w) { cin >> u >> v >> w; outd[u-1]++; ind[v-1]++; } void Creat() { for(int i = 0; i < n; i++) { adj[i].data = nadj[i].data = i+1;//结点标号从1到n adj[i].firstarc = nadj[i].firstarc = NULL; } for(int i = 1; i <= m; i++) { int u, v, w; GetArc(u, v, w); //cout << u << " " << v << " "<< w << endl; ArcNode *p = &arc[top++]; //建立邻接表 p->adjvex = v; p->dut = w; p->nextarc = adj[u-1].firstarc; adj[u-1].firstarc = p; //建立逆邻接表 ArcNode *q = new ArcNode; q->adjvex = u; q->dut = w;///////////////////////////////////这里忘了 q->nextarc = nadj[v-1].firstarc; nadj[v-1].firstarc = q;//////////少写了个n，无语……因为这个n，正top排序和逆top排序都惨了 } } void Critical() { int i = 0, j, k; ArcNode *p; i=0;//边计数器置初值 for(j=0;j<n;j++) //扫描顶点表，依次取顶点v(j+1) { p=adj[j].firstarc; while(p) //扫描顶点的v(j+1)的出边表 {//计算各边(v(j+1),v(k+1))所代表的活动a(i+1)的e[i]和l[i] k=p->adjvex-1; e[++i]=ve[j]; l[i]=vl[k]-p->dut; printf("%d %d %d %d %d ",//输出活动a(i+1)的有关信息 adj[j].data,adj[k].data,e[i],l[i],l[i]-e[i]); if(l[i]==e[i])//关键活动 printf("关键活动"); printf(" "); p=p->nextarc; } } } void Print2() { printf("每个事件的最早开始时间 "); for(int i = 0; i < n; i++) printf("%d ", ve[i]); printf(" 每个事件的最晚开始时间 "); for(int j = 0; j < n; j++) printf("%d ", vl[j]); printf(" "); } /* 我的测试数据 9 11 1 2 6 1 3 4 1 4 5 2 5 1 3 5 1 4 6 2 5 7 9 5 8 7 6 8 4 7 9 2 8 9 4 */ /* AOE网 注意事件的最早发生时间和最晚发生时间是一样的 即vl(n) = ve(n) ve(j)的求法 从v(1) = 0开始递推 v(j) = max{v(i)+dut<i, j>} 其中<i, j> 属于T，T是所有以j顶点为头的点的集合 2 <= j <= n; vl(j)的求法， vl(j)是从vl(n)开始推的，因为vl(N) = ve(n) v(j) = min{v(i)-dut<i, j>}; <i, j> 属于S， 1 <= i <= n-1; 其中S是所有以i为尾的弧的集合 关键路径的算法： 1：建立图的邻接表和逆邻接表 2：利用邻接表求顶点的出度，利用逆邻接表算定点的入度 3：利用拓扑排序求事件顶点的最早发生时间 4：利用逆向拓扑排序的算法求事件节点的最晚发生时间 5：利用3和4求得的事件的最早发生时间和最晚发生时间求活动的最早发生时间和最晚发生时间 */