(1)对一个描述工程的 AOE 网,建立其存储结构;(注:数据的输入可以是键盘输入或文件输入两种方式) (2)判断该 AOE 网是否能够顺利进行。 (3)若该工程能顺利进行,输出完成整项工程至少需要多少时间,以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。(注:结果的输出可以是屏幕输出和文件输出两种方式) 根据以上要求,以c++为代码语言,设计程序
时间: 2024-04-14 09:26:07 浏览: 32
以下是使用 C++ 语言设计的程序示例。程序实现了对一个描述工程的 AOE 网的存储结构、判断该 AOE 网是否能够顺利进行以及输出完成整项工程所需的时间和关键活动的相关信息。
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 任务节点的结构体
struct Node {
int id; // 任务节点的编号
int duration; // 任务节点的持续时间
int earliestTime; // 最早发生时间
int latestTime; // 最迟发生时间
bool isCritical; // 是否为关键活动
vector<int> nextNodes; // 后继节点列表
};
// 存储整个工程的AOE网结构体
struct AOE_Network {
vector<Node> nodes; // 任务节点列表
};
// 判断AOE网是否能够顺利进行
bool canProceed(AOE_Network& network) {
// 统计每个任务节点的入度
vector<int> inDegrees(network.nodes.size(), 0);
for (const auto& node : network.nodes) {
for (int nextNode : node.nextNodes) {
inDegrees[nextNode]++;
}
}
// 使用拓扑排序判断是否有环
queue<int> q;
for (int i = 0; i < inDegrees.size(); i++) {
if (inDegrees[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int currNode = q.front();
q.pop();
for (int nextNode : network.nodes[currNode].nextNodes) {
inDegrees[nextNode]--;
if (inDegrees[nextNode] == 0) {
q.push(nextNode);
}
}
}
// 如果存在环,返回false;否则返回true
for (int inDegree : inDegrees) {
if (inDegree > 0) {
return false;
}
}
return true;
}
// 计算关键路径和最早发生时间
void calculateCriticalPath(AOE_Network& network) {
int numNodes = network.nodes.size();
// 初始化最早发生时间为0
for (int i = 0; i < numNodes; i++) {
network.nodes[i].earliestTime = 0;
}
// 计算最早发生时间
for (int i = 0; i < numNodes; i++) {
int currNode = i;
for (int nextNode : network.nodes[currNode].nextNodes) {
int finishTime = network.nodes[currNode].earliestTime + network.nodes[currNode].duration;
if (finishTime > network.nodes[nextNode].earliestTime) {
network.nodes[nextNode].earliestTime = finishTime;
}
}
}
// 寻找最后一个任务节点的最早发生时间,即整项工程的完成时间
int maxFinishTime = 0;
for (int i = 0; i < numNodes; i++) {
int currFinishTime = network.nodes[i].earliestTime + network.nodes[i].duration;
if (currFinishTime > maxFinishTime) {
maxFinishTime = currFinishTime;
}
}
// 初始化最迟发生时间为整项工程的完成时间
for (int i = 0; i < numNodes; i++) {
network.nodes[i].latestTime = maxFinishTime;
}
// 计算最迟发生时间
for (int i = numNodes - 1; i >= 0; i--) {
int currNode = i;
for (int nextNode : network.nodes[currNode].nextNodes) {
int startTime = network.nodes[nextNode].latestTime - network.nodes[nextNode].duration;
if (startTime < network.nodes[currNode].latestTime) {
network.nodes[currNode].latestTime = startTime;
}
}
}
// 判断关键活动
for (int i = 0; i < numNodes; i++) {
int finishTime = network.nodes[i].earliestTime + network.nodes[i].duration;
if (finishTime == network.nodes[i].latestTime) {
network.nodes[i].isCritical = true;
}
}
}
// 输出完成整项工程所需的时间和关键活动的相关信息
void printCriticalPath(AOE_Network& network) {
cout << "完成整项工程所需时间:" << network.nodes[0].latestTime << " 时间单位" << endl;
cout << "关键活动的信息:" << endl;
for (const auto& node : network.nodes) {
if (node.isCritical) {
cout << "关键活动:" << node.id << endl;
cout << "前驱节点:";
for (int prevNode : node.nextNodes) {
cout << prevNode << " ";
}
cout << endl;
cout << "最早发生时间:" << node.earliestTime << " 时间单位" << endl;
cout << "最迟发生时间:" << node.latestTime << " 时间单位" << endl;
cout << endl;
}
}
}
int main() {
AOE_Network network;
// 从键盘输入或文件输入读取任务节点和依赖关系,并构建AOE网存储结构
// 这里省略具体的输入代码,可以根据需要自行完成
// 判断AOE网是否能够顺利进行
bool canProceedFlag = canProceed(network);
if (canProceedFlag) {
cout << "该工程能够顺利进行!" << endl;
// 计算关键路径和最早/最迟发生时间
calculateCriticalPath(network);
// 输出完成整项工程所需的时间和关键活动的相关信息
printCriticalPath(network);
}
else {
cout << "该工程不能顺利进行!" << endl;
}
return 0;
}
```
请注意,上述代码仅提供了一个程序框架,需要根据具体的输入和实际情况进行适当的修改和完善。