c++生成AOE网求出每个事件的最早开始时间及最迟开始时间。 再求出每个事件的最早发生时间及最迟发生时间及时间余量。由此确认关键活动及关键路径。
时间: 2023-09-03 07:05:54 浏览: 59
好的,这是一个比较具体的问题。在C++中生成AOE网,可以使用图论中的邻接表或邻接矩阵来表示。然后,可以使用拓扑排序算法来求出每个事件的最早开始时间和最早发生时间,以及确认关键路径。
以下是一个简单的C++代码示例,用于生成AOE网和计算关键路径:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 10010;
struct Edge {
int to;
int weight;
int next;
} edge[N];
int head[N];
int cnt = 0;
int n, m;
int in_degree[N];
int earliest_time[N];
int latest_time[N];
bool is_critical[N];
void addEdge(int u, int v, int w) {
edge[++cnt].to = v;
edge[cnt].weight = w;
edge[cnt].next = head[u];
head[u] = cnt;
}
void init() {
memset(head, -1, sizeof(head));
memset(in_degree, 0, sizeof(in_degree));
memset(earliest_time, 0, sizeof(earliest_time));
memset(latest_time, 0x3f, sizeof(latest_time));
memset(is_critical, false, sizeof(is_critical));
cnt = 0;
}
void topoSort() {
queue<int> que;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
que.push(i);
earliest_time[i] = 0;
}
}
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].weight;
in_degree[v]--;
earliest_time[v] = max(earliest_time[v], earliest_time[u] + w);
if (in_degree[v] == 0) {
que.push(v);
}
}
}
}
void calcLatestTime() {
queue<int> que;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
que.push(i);
latest_time[i] = earliest_time[n];
}
}
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].weight;
in_degree[v]--;
latest_time[u] = min(latest_time[u], latest_time[v] - w);
if (in_degree[v] == 0) {
que.push(v);
}
}
}
}
void calcCritical() {
for (int i = 1; i <= n; i++) {
if (earliest_time[i] == latest_time[i]) {
is_critical[i] = true;
}
}
}
int main() {
cin >> n >> m;
init();
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
addEdge(u, v, w);
in_degree[v]++;
}
topoSort();
calcLatestTime();
calcCritical();
cout << "每个事件的最早开始时间:\n";
for (int i = 1; i <= n; i++) {
cout << earliest_time[i] << " ";
}
cout << endl;
cout << "每个事件的最晚开始时间:\n";
for (int i = 1; i <= n; i++) {
cout << latest_time[i] << " ";
}
cout << endl;
cout << "每个事件的最早发生时间:\n";
for (int i = 1; i <= n; i++) {
cout << earliest_time[i] << " ";
}
cout << endl;
cout << "每个事件的最晚发生时间:\n";
for (int i = 1; i <= n; i++) {
cout << latest_time[i] << " ";
}
cout << endl;
cout << "关键活动:\n";
for (int i = 1; i <= cnt; i++) {
int u = edge[i].to;
int v = i;
int w = edge[i].weight;
if (is_critical[u] && earliest_time[u] + w == earliest_time[v] && latest_time[u] == latest_time[v] - w) {
cout << u << " -> " << v << endl;
}
}
return 0;
}
```
这段代码中,我们使用邻接表来表示图,使用拓扑排序算法求出每个事件的最早开始时间和最早发生时间,然后使用反向拓扑排序和计算最晚开始时间和最晚发生时间。最后,判断每个活动是否是关键活动,输出关键路径。
希望这个代码示例可以帮到您!