设计算法求解AOE网的关键路径，写出c++代码

下面是使用 C++ 语言实现求解 AOE 网关键路径的代码：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

const int INF = 0x3f3f3f3f;

// AOE 网的边的结构体
struct Edge {
    int to;         // 边的终点
    int weight;     // 边的权重
    Edge(int t, int w) : to(t), weight(w) {}
};

// AOE 网的节点的结构体
struct Node {
    int id;                 // 节点的编号
    int earliest_start;     // 最早开始时间
    int latest_start;       // 最晚开始时间
    vector<Edge> edges;     // 节点的出边
};

// 拓扑排序
vector<Node> topological_sort(vector<Node>& nodes, int start) {
    vector<Node> sorted;    // 拓扑排序后的节点序列
    queue<Node> q;          // 存储入度为 0 的节点
    vector<int> in_degree(nodes.size(), 0);  // 存储每个节点的入度

    // 计算每个节点的入度
    for (const auto& n : nodes) {
        for (const auto& e : n.edges) {
            in_degree[e.to]++;
        }
    }

    // 将入度为 0 的节点加入队列
    q.push(nodes[start]);
    while (!q.empty()) {
        Node n = q.front();
        q.pop();
        sorted.push_back(n);

        for (const auto& e : n.edges) {
            in_degree[e.to]--;
            if (in_degree[e.to] == 0) {
                q.push(nodes[e.to]);
            }
        }
    }

    return sorted;
}

// 计算 AOE 网的关键路径
vector<int> critical_path(vector<Node>& nodes, int start, int end) {
    // 拓扑排序
    vector<Node> sorted_nodes = topological_sort(nodes, start);

    // 初始化节点的最早开始时间和最晚开始时间
    for (auto& n : nodes) {
        n.earliest_start = 0;
        n.latest_start = INF;
    }
    nodes[start].latest_start = nodes[start].earliest_start;

    // 计算每个节点的最早开始时间
    for (const auto& n : sorted_nodes) {
        for (const auto& e : n.edges) {
            int cur_es = nodes[e.to].earliest_start;
            int new_es = n.earliest_start + e.weight;
            if (cur_es < new_es) {
                nodes[e.to].earliest_start = new_es;
            }
        }
    }

    // 计算每个节点的最晚开始时间
    for (auto it = sorted_nodes.rbegin(); it != sorted_nodes.rend(); it++) {
        for (const auto& e : it->edges) {
            int cur_ls = it->latest_start;
            int new_ls = nodes[e.to].latest_start - e.weight;
            if (cur_ls > new_ls) {
                it->latest_start = new_ls;
            }
        }
    }

    // 找出关键路径上的节点
    vector<int> critical_nodes;
    for (const auto& n : nodes) {
        for (const auto& e : n.edges) {
            int activity_time = nodes[e.to].latest_start - n.earliest_start - e.weight;
            if (activity_time == 0) {
                critical_nodes.push_back(n.id);
                critical_nodes.push_back(e.to);
            }
        }
    }

    return critical_nodes;
}

int main() {
    // 创建 AOE 网
    vector<Node> nodes = {
        {0, 0}, // 起点
        {1},
        {2},
        {3},
        {4},
        {5},
        {6},
        {7},
        {8},
        {9},
        {10},
        {11},
        {12, INF} // 终点
    };
    nodes[0].edges = { Edge(1, 6), Edge(2, 4), Edge(3, 5) };
    nodes[1].edges = { Edge(4, 1) };
    nodes[2].edges = { Edge(4, 1), Edge(5, 2) };
    nodes[3].edges = { Edge(5, 3) };
    nodes[4].edges = { Edge(6, 9) };
    nodes[5].edges = { Edge(6, 7), Edge(7, 4) };
    nodes[6].edges = { Edge(8, 2) };
    nodes[7].edges = { Edge(8, 4) };
    nodes[8].edges = { Edge(9, 7) };
    nodes[9].edges = { Edge(12, 3) };
    nodes[10].edges = { Edge(4, 1), Edge(7, 5), Edge(11, 8) };
    nodes[11].edges = { Edge(9, 2), Edge(12, 4) };
    nodes[12].edges = {};

    // 计算关键路径
    vector<int> critical_nodes = critical_path(nodes, 0, 12);

    // 输出关键路径上的节点
    cout << "Critical path: ";
    for (auto n : critical_nodes) {
        cout << n << " ";
    }
    cout << endl;

    return 0;
}

以上代码可以计算出 AOE 网的关键路径，并输出关键路径上的节点。