用c语言求aoe网的关键路径

AOE网（Activity On Edge）也叫 PERT 图，是一种用于表示项目进度计划的网络图。在 AOE 网中，每个事件作为一个节点，每个活动作为一条有向边。每个事件和活动都有一个时间长度。关键路径指的是连接起点和终点的路径，这条路径上的活动所需要的时间总和最长，因此决定了整个项目的最短完成时间。

要求 AOE 网的关键路径，可以使用 C 语言实现关键路径算法。具体的实现步骤如下：

1. 定义一个结构体来表示 AOE 网中的节点，包括节点编号、活动编号、活动持续时间、前继节点个数、后继节点个数、前继节点和后继节点数组等信息。

2. 构建 AOE 网，读入每个节点的信息，建立节点之间的关系。

3. 计算每个节点的最早开始时间 EST 和最迟开始时间 LST，以及每个活动的最早开始时间 EFT 和最迟开始时间 LFT。通过这些时间可以确定关键路径上的活动。

4. 输出关键路径上的活动，并计算整个项目的最短完成时间。

下面是 C 语言实现关键路径算法的伪代码：

struct node {
    int id;             // 节点编号
    int act_id;         // 活动编号
    int act_time;       // 活动持续时间
    int pred_cnt;       // 前继节点个数
    int succ_cnt;       // 后继节点个数
    int *preds;         // 前继节点数组
    int *succs;         // 后继节点数组
    int est, lst;       // 最早开始时间、最迟开始时间
    int eft, lft;       // 最早结束时间、最迟结束时间
};

int main() {
    // 构建 AOE 网
    struct node nodes[N];
    int n = read_input(nodes);
    build_network(nodes, n);

    // 计算 EST 和 LST
    calc_est_lst(nodes, n);

    // 计算 EFT 和 LFT
    calc_eft_lft(nodes, n);

    // 输出关键路径上的活动
    print_critical_activities(nodes, n);

    // 计算项目最短完成时间
    int project_time = calc_project_time(nodes, n);
    printf("Project time: %d\n", project_time);

    return 0;
}

其中，`read_input()` 函数用于读入 AOE 网中的节点信息，`build_network()` 函数用于构建节点之间的关系，`calc_est_lst()` 函数用于计算每个节点的最早开始时间 EST 和最迟开始时间 LST，`calc_eft_lft()` 函数用于计算每个活动的最早开始时间 EFT 和最迟开始时间 LFT，`print_critical_activities()` 函数用于输出关键路径上的活动，`calc_project_time()` 函数用于计算整个项目的最短完成时间。