AOE/AOV网下的关键路径
在做那本王道考研数据结构书的时候发现这个东西，以前没听说过（太菜了
1.定义
一般而言这个模型可以用来表示一个项目的子项之间的依赖关系，用来管理项目进度。
1.1 AOV网
AOV网指的是Activity-On-Vertex，用点表示事件，用边表示事件之间的关系（活动），边权是活动时间。这是一个DAG（有向无环图）
1.2 AOE网
AOE网指的是Activity-On-Edge，用点表示事件，用边表示事件之间的关系（活动），边权是活动时间。这也是一个DAG（有向无环图）
1.3 关键路径
如果改变一条路径上的任意一条边的边权，都可以加速项目的最终进度，那么这条路径被称为关键路径。
2.计算方法
计算关键路径事实上只是在DAG上的简单dp，首先计算一个事件的最早开始时间，然后计算一个事件的不会影响到最终项目进度的最晚开始时间，当最早开始时间等于最晚开始时间，那么这个点是一个关键的点。所有的关键点一定会组成一颗树。树上的所有路径都是关键路径。
首先计算拓扑序，然后在拓扑序上正向递推一个事件的最早开始时间，最后在逆拓扑序上递推最迟开始时间
$$
for\ each\ edge\ <u \rightarrow v> \ :
$$
$$
\begin{aligned}
minStartTime[v] &= Max(minStartTime[v],minStartTime[u]+w[u][v])\\
maxStartTime[u] &= Min(maxStartTime[u],maxStartTime[v]-w[u][v])
\end{aligned}
$$
第一个点的 minStartTime = 0，最后一个点的 maxStartTime = minStartTime
3.代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1e6+7, INF = 0x3f3f3f3f;
template <typename _TP>
inline _TP qread(_TP &X){
char ch=0;int w;X=0;
while(!isdigit(ch)){w=ch=='-';ch=getchar();}
while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^'0');ch=getchar();}
X=w?-X:X;
return X;
}
queue <int> q;
vector <int> v[MAXN],d[MAXN],pre[MAXN],predis[MAXN];
int ind[MAXN];
inline void adde(const int x,const int y,const int z){
v[x].push_back(y);
d[x].push_back(z);
pre[y].push_back(x);
predis[y].push_back(z);
ind[y]++;
}
int topoOrder[MAXN],vis[MAXN],cntTopo=0;
void topoSort(int s){
vis[s]=1;
q.push(s);
int nxt;
while(!q.empty()){
s = q.front();
vis[s]=1;
q.pop();
topoOrder[++cntTopo]=s;
for(int i=0;i<v[s].size();i++){
nxt = v[s][i];
if(!vis[nxt]){
if(!(--ind[nxt])){
q.push(nxt);
}
}
}
}
}
int minStart[MAXN],maxStart[MAXN],n,m;
bool iscritical [MAXN];
inline int Max(const int a,const int b){
return a>b?a:b;
}
inline int Min(const int a,const int b){
return a<b?a:b;
}
inline void PRINT(const int *tmp){
for(int i=1;i<=n;i++){
cout<<tmp[i]<<' ';
}
cout<<'\n';
}
int main(){
int x,y,z;
qread(n);qread(m);
for(int i=1;i<=m;i++){
qread(x);qread(y);qread(z);
adde(x,y,z);
}
int s=1;
topoSort(s);
cout<<"topoOrder: ";
PRINT(topoOrder);
int now,nxt;
for(int i=1;i<=n;i++){
now = topoOrder[i];
for(int j=0;j<v[now].size();j++){
nxt = v[now][j];
minStart[nxt] = Max(minStart[nxt],minStart[now]+d[now][j]);
}
}
cout<<"minStart: ";
PRINT(minStart);
memset(maxStart,0x3f,sizeof(maxStart));
maxStart[topoOrder[n]] = minStart[topoOrder[n]];
for(int i=n;i>=1;i--){
now = topoOrder[i];
for(int j=0;j<pre[now].size();j++){
nxt = pre[now][j];
maxStart[nxt] = Min(maxStart[nxt],maxStart[now]-predis[now][j]);
}
}
cout<<"maxStart: ";
PRINT(maxStart);
for(int i=1;i<=n;i++){
for(int j=0;j<v[i].size();j++){
nxt = v[i][j];
int minHappen = minStart[i];
int maxHappen = maxStart[nxt]-d[i][j];
if(maxHappen - minHappen == 0){
iscritical[i] = iscritical [j] = true;
}
}
}
cout<<"critical point: ";
for(int i=1;i<=n;i++){
if(iscritical[i])cout<<i<<' ';
}
return 0;
}
|
4.样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 10 14
1 2 5
1 3 6
2 5 3
3 5 6
3 4 3
4 5 3
4 7 1
4 8 4
5 6 4
5 7 2
6 10 4
7 9 5
8 9 2
9 10 2
|
第一行n,m是点的数量和边的数量
样例来自王道数据结构考研复习指导的习题13
