请设计int pathNum(AOENetwork g)函数。 该函数返回AOE网g中关键路径数目。 已知点表中第一个点是源点,最后一个点是汇点,并且事件和活动的时间都已经计算好。 请注意,本题有预置代码,只需提交所要求的函数定义代码即可。
时间: 2024-03-25 09:39:14 浏览: 52
以下是所要求的函数定义代码:
```c++
int pathNum(AOENetwork g) {
int num = 0;
int n = g.vertexNum();
// 计算每个活动的最早开始时间(ES)和最晚开始时间(LS),以及最早完成时间(EF)和最晚完成时间(LF)
vector<int> es(n, 0);
vector<int> ls(n, 0);
vector<int> ef(n, 0);
vector<int> lf(n, 0);
g.topoSort(es, ef);
// 计算每个活动的最晚开始时间(LS)和最晚完成时间(LF)
for (int i = n - 1; i >= 0; i--) {
int v = g.getVertex(i);
ls[v] = ef[v];
for (int j = 0; j < g.outDegree(v); j++) {
int w = g.getOutNeighbor(v, j);
ls[v] = min(ls[v], es[w] - g.getWeight(v, w));
}
lf[v] = ls[v] + g.getDuration(v);
}
// 统计关键路径数目
for (int i = 0; i < n; i++) {
int v = g.getVertex(i);
for (int j = 0; j < g.outDegree(v); j++) {
int w = g.getOutNeighbor(v, j);
if (ef[v] == es[w] && lf[v] == ls[w] + g.getWeight(v, w)) {
num++;
}
}
}
return num;
}
```
该函数的实现过程如下:
1. 首先计算每个活动的最早开始时间(ES)和最早完成时间(EF),并且按照拓扑排序的顺序存储在数组es和ef中。
2. 然后计算每个活动的最晚开始时间(LS)和最晚完成时间(LF),并且按照逆拓扑排序的顺序存储在数组ls和lf中。
3. 最后统计关键路径的数目。对于每个活动,如果它的最早开始时间等于前一个活动的最早完成时间,且它的最晚完成时间等于后一个活动的最晚开始时间,那么这个活动就在关键路径上。统计所有在关键路径上的活动即可得到关键路径数目。