用c++实现输入一个aoe网并求关键路径

以下是用C++实现输入一个AOE网并求关键路径的代码和步骤：

1.首先定义一个结构体来表示AOE网中的每个节点，包括节点的编号、最早开始时间、最晚开始时间、活动持续时间、入度、出度和后继节点等信息。

struct Node {
    int id; // 节点编号
    int earliest_start; // 最早开始时间
    int latest_start; // 最晚开始时间
    int duration; // 活动持续时间
    int in_degree; // 入度
    int out_degree; // 出度
    vector<int> successors; // 后继节点
};

2.然后定义一个函数来读取AOE网的信息，包括节点数、边数和每条边的起点、终点和持续时间等信息，并根据这些信息构建AOE网的邻接表。

void read_graph(int n, int m, vector<Node>& graph) {
    for (int i = 1; i <= n; i++) {
        graph.push_back({i, 0, 0, 0, 0, 0, {}});
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u - 1].successors.push_back(v - 1);
        graph[u - 1].out_degree++;
        graph[v - 1].in_degree++;
        graph[v - 1].duration = w;
    }
}

3.接下来定义一个函数来计算每个节点的最早开始时间和最晚开始时间，并根据这些信息求出关键路径。

void critical_path(int n, vector<Node>& graph) {
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (graph[i].in_degree == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < graph[u].successors.size(); i++) {
            int v = graph[u].successors[i];
            graph[v].earliest_start = max(graph[v].earliest_start, graph[u].earliest_start + graph[u].duration);
            graph[v].in_degree--;
            if (graph[v].in_degree == 0) {
                q.push(v);
            }
        }
    }
    int last_node = n - 1;
    graph[last_node].latest_start = graph[last_node].earliest_start;
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j < graph[i].successors.size(); j++) {
            int v = graph[i].successors[j];
            graph[i].latest_start = max(graph[i].latest_start, graph[v].latest_start - graph[i].duration);
        }
    }
    vector<int> path;
    for (int i = 0; i < n; i++) {
        if (graph[i].earliest_start == graph[i].latest_start) {
            path.push_back(graph[i].id);
        }
    }
    cout << "The critical path is: ";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i] << " ";
    }
    cout << endl;
}

4.最后在主函数中调用上述函数即可。

int main() {
    int n, m;
    cin >> n >> m;
    vector<Node> graph;
    read_graph(n, m, graph);
    critical_path(n, graph);
    return 0;
}