aoe网络的关键路径c++实现

AOE网络（Activity On Edge Network）是一种用来描述工程项目的网络模型，其中每个节点表示一个活动，每条边表示活动之间的先后关系。关键路径是指在保证项目完成时间最短的前提下，所有活动中耗时最长的路径。以下是用C++实现关键路径的示例代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 10010;
const int INF = 0x7fffffff;

struct Edge {
    int to, w;
    Edge(int to, int w) : to(to), w(w) {}
};

vector<Edge> G[MAXN]; // 存储图
int inDegree[MAXN]; // 存储入度
int earliest[MAXN]; // 存储最早开始时间
int latest[MAXN]; // 存储最晚开始时间
int n, m; // n为节点数，m为边数

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
            earliest[i] = 0;
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto e : G[u]) {
            int v = e.to, w = e.w;
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
            earliest[v] = max(earliest[v], earliest[u] + w);
        }
    }
}

int criticalPath() {
    topsort();
    int res = 0;
    for (int u = 1; u <= n; ++u) {
        for (auto e : G[u]) {
            int v = e.to, w = e.w;
            latest[u] = max(latest[u], latest[v] - w);
        }
    }
    for (int u = 1; u <= n; ++u) {
        for (auto e : G[u]) {
            int v = e.to, w = e.w;
            if (latest[v] - earliest[u] - w == 0) {
                res = max(res, latest[v]);
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));
        inDegree[v]++;
    }
    cout << criticalPath() << endl;
    return 0;
}

在上述代码中，我们使用vector存储图，使用队列进行拓扑排序。在拓扑排序的过程中，我们计算每个节点的最早开始时间。之后，我们再次遍历图，计算每个节点的最晚开始时间，并且计算关键路径的长度。