AOE 网

action on edge

1. 点为事件，边为活动
2. 边权为活动需要时间
3. 入度边全都完成，点才发生

关键时间点

1. 事件最早发生时间 $v_{e}(k)$
   1. ve[SRC] = 0
   2. ve[to] = max(ve[from] + w ...)
2. 事件最迟发生时间 $v_{l}(k)$
   1. vl[DST]=ve[DST]
   2. vl[from] = min(vl[to] - w ...)
3. 活动最早开始时间 $a_{e}(k)$
   1. ae[from, to] = ve[from]
4. 活动最迟开始时间 $a_{l}(k)$
   1. al[from, to] = vl[to] - w
5. 差额 $a_{d}(k)$
   1. ad[from, to] = al - ae
6. 关键活动 := ad = 0

关键路径

• 定义 := 由关键活动构成的路径
• 性质
  1. 关键路径不唯一
  2. 缩短被所有关键路径共用的路段才能缩短工期