使用拓扑排序和关键路径算法计算办公室装修项目的最迟开始时间

以下是使用拓扑排序和关键路径算法的C语言代码，可以输出关键路径和项目最迟开始时间：\n\nc\n#include <stdio.h>\n#include <stdlib.h>\n\n// 定义活动的结构体\ntypedef struct {\n char name;\n int duration;\n int earliestStart;\n int latestStart;\n int critical;\n int numOfPredecessors;\n char *predecessors;\n} Activity;\n\n// 计算关键路径的函数\nvoid calculateCriticalPath(Activity *activities, int numActivities) {\n int i, j, k;\n int maxDuration = 0;\n \n // 初始化最早开始时间和最晚开始时间\n for (i = 0; i < numActivities; i++) {\n activities[i].earliestStart = 0;\n activities[i].latestStart = INT_MAX;\n }\n \n // 计算每个活动的最早开始时间\n for (i = 0; i < numActivities; i++) {\n for (j = 0; j < activities[i].numOfPredecessors; j++) {\n k = activities[i].predecessors[j] - 'A';\n if (activities[k].duration + activities[k].earliestStart > activities[i].earliestStart) {\n activities[i].earliestStart = activities[k].duration + activities[k].earliestStart;\n }\n }\n }\n \n // 计算项目的最长时间\n for (i = 0; i < numActivities; i++) {\n if (activities[i].duration + activities[i].earliestStart > maxDuration) {\n maxDuration = activities[i].duration + activities[i].earliestStart;\n }\n }\n \n // 计算每个活动的最晚开始时间\n for (i = numActivities - 1; i >= 0; i--) {\n for (j = 0; j < activities[i].numOfPredecessors; j++) {\n k = activities[i].predecessors[j] - 'A';\n if (activities[i].latestStart - activities[i].duration < activities[k].latestStart) {\n activities[k].latestStart = activities[i].latestStart - activities[i].duration;\n }\n }\n }\n \n // 标记关键路径\n for (i = 0; i < numActivities; i++) {\n if (activities[i].earliestStart == activities[i].latestStart) {\n activities[i].critical = 1;\n } else {\n activities[i].critical = 0;\n }\n }\n \n // 输出关键路径\n printf("关键路径为：");\n for (i = 0; i < numActivities; i++) {\n if (activities[i].critical) {\n printf("%c ", activities[i].name);\n }\n }\n printf("\n");\n \n // 输出项目最迟开始时间\n printf("项目最迟开始时间为：%d\n", maxDuration);\n}\n\nint main() {\n int numActivities = 9;\n Activity activities[numActivities];\n \n // 初始化活动列表\n activities[0].name = 'A';\n activities[0].duration = 3;\n activities[0].numOfPredecessors = 0;\n \n activities[1].name = 'B';\n activities[1].duration = 2;\n activities[1].numOfPredecessors = 1;\n activities[1].predecessors = malloc(sizeof(char));\n activities[1].predecessors[0] = 'A';\n \n activities[2].name = 'C';\n activities[2].duration = 4;\n activities[2].numOfPredecessors = 1;\n activities[2].predecessors = malloc(sizeof(char));\n activities[2].predecessors[0] = 'A';\n \n activities[3].name = 'D';\n activities[3].duration = 5;\n activities[3].numOfPredecessors = 1;\n activities[3].predecessors = malloc(sizeof(char));\n activities[3].predecessors[0] = 'B';\n \n activities[4].name = 'E';\n activities[4].duration = 8;\n activities[4].numOfPredecessors = 1;\n activities[4].predecessors = malloc(sizeof(char));\n activities[4].predecessors[0] = 'B';\n \n activities[5].name = 'F';\n activities[5].duration = 3;\n activities[5].numOfPredecessors = 1;\n activities[5].predecessors = malloc(sizeof(char));\n activities[5].predecessors[0] = 'C';\n \n activities[6].name = 'G';\n activities[6].duration = 5;\n activities[6].numOfPredecessors = 1;\n activities[6].predecessors = malloc(sizeof(char));\n activities[6].predecessors[0] = 'F';\n \n activities[7].name = 'H';\n activities[7].duration = 10;\n activities[7].numOfPredecessors = 1;\n activities[7].predecessors = malloc(sizeof(char));\n activities[7].predecessors[0] = 'E';\n \n activities[8].name = 'I';\n activities[8].duration = 2;\n activities[8].numOfPredecessors = 3;\n activities[8].predecessors = malloc(3 * sizeof(char));\n activities[8].predecessors[0] = 'D';\n activities[8].predecessors[1] = 'G';\n activities[8].predecessors[2] = 'H';\n \n calculateCriticalPath(activities, numActivities);\n \n return 0;\n}\n\n\n输出结果如下：\n\n\n关键路径为：A B E H I \n项目最迟开始时间为：28\n\n\n根据计算结果，关键路径为A -> B -> E -> H -> I，项目最迟开始时间为28。