用C++通过aoe网和关键路径,求出每个事件的最早开始时间及最迟开始时间。 再求出每个事件的最早发生时间及最迟发生时间及时间余量。由此确认关键活动及关键路径。给出代码
时间: 2023-09-03 22:16:36 浏览: 51
以下是通过C++实现求解AOE网和关键路径的代码,其中假设AOE网中所有活动的时间都是确定的,不考虑随机因素:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 10000;
int n, m; // n表示节点数,m表示边数
int earliest[MAXN], latest[MAXN], slack[MAXN]; // 记录每个节点的最早开始时间、最迟开始时间和时间余量
int head[MAXN], nxt[MAXN], to[MAXN], weight[MAXN], cnt; // 存储图的信息
int inDegree[MAXN]; // 记录每个节点的入度
vector<int> criticalPath; // 存储关键路径上的节点
void addEdge(int u, int v, int w) {
to[++cnt] = v;
weight[cnt] = w;
nxt[cnt] = head[u];
head[u] = cnt;
inDegree[v]++;
}
void topologicalSort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
earliest[i] = 0;
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
earliest[v] = max(earliest[v], earliest[u] + weight[i]);
if (--inDegree[v] == 0) {
q.push(v);
}
}
}
}
void calcLatest() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
latest[i] = earliest[n];
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
latest[u] = min(latest[u], latest[v] - weight[i]);
if (--inDegree[v] == 0) {
q.push(v);
}
}
}
}
void calcSlack() {
for (int u = 1; u <= n; u++) {
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
slack[i] = latest[v] - earliest[u] - weight[i];
}
}
}
void findCriticalPath() {
for (int i = 1; i <= m; i++) {
if (slack[i] == 0) {
criticalPath.push_back(to[i]);
}
}
}
int main() {
cin >> n >> m;
cnt = 0;
memset(head, 0, sizeof(head));
memset(inDegree, 0, sizeof(inDegree));
memset(earliest, 0, sizeof(earliest));
memset(latest, 0x7f, sizeof(latest));
memset(slack, 0, sizeof(slack));
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
}
topologicalSort();
calcLatest();
calcSlack();
findCriticalPath();
cout << "节点的最早开始时间为:" << endl;
for (int i = 1; i <= n; i++) {
cout << i << ": " << earliest[i] << endl;
}
cout << "节点的最迟开始时间为:" << endl;
for (int i = 1; i <= n; i++) {
cout << i << ": " << latest[i] << endl;
}
cout << "节点的时间余量为:" << endl;
for (int i = 1; i <= m; i++) {
cout << i << ": " << slack[i] << endl;
}
cout << "关键路径上的节点为:" << endl;
for (int i = 0; i < criticalPath.size(); i++) {
cout << criticalPath[i] << " ";
}
cout << endl;
return 0;
}
```
这段代码实现了AOE网的拓扑排序、求解最早开始时间、最迟开始时间和时间余量,并且找出了关键路径上的节点。