本文共 1403 字，大约阅读时间需要 4 分钟。
#include#include #include #include #include #include using namespace std;const int MAXV = 510;const int INF = 1000000000;int inDegree[MAXV], n, m;int ve[MAXV], vl[MAXV], e[MAXV], l[MAXV];struct Node{ int v; // 顶点编号 int w; // 边权 };vector G[MAXV];stack topOrder;bool topologicalSort(){ queue q; for(int i = 0; i < n; i++) { if(inDegree[i] == 0) { q.push(i); } } while(!q.empty()) { int u = q.front(); q.pop(); topOrder.push(u); // 加入拓扑序列 for(int i = 0; i < G[u].size(); i++) { int v = G[u][i].v; inDegree[v]--; if(inDegree[v] == 0) { q.push(v); } // 用 ve[u] 来更新所有后继节点 v if(ve[u] + G[u][i].w > ve[v]) { ve[v] = ve[u] + G[u][i].w; } } } if(topOrder.size() == n) return true; else return false;} int CriticalPath(){ memset(ve, 0, sizeof(ve)); if(topologicalSort() == false) { return -1; } fill(vl, vl + n, ve[n - 1]); // vl 数组初始化， 初始值为汇点 ve 的值 while(!topOrder.empty()) { int u = topOrder.top(); topOrder.pop(); for(int i = 0; i < G[u].size(); i++) { int v = G[u][i].v; // 用 u 的所有后继结点 v 的 vl 值来更新 vl[u] if(vl[v] - G[u][i].w < vl[u]) { vl[u] = vl[v] - G[u][i].w; } } } // 遍历邻接表所有的边，计算活动的最早开始时间 e 和最迟开始时间 l for(int u = 0; u < n; u++) { for(int i = 0; i < G[u].size(); i++) { int v = G[u][i].v, w = G[u][i].w; int e = ve[u], l = vl[v] - w; if(e == l) { printf("%d -> %d", u, v); } } } return ve[n - 1]; // 返回关键路径长度 }int main(){ // ...... return 0;}
转载地址：http://jetmi.baihongyu.com/