No.468

$i$ の最早結合点時刻 $f(i)$ は $i$ に入る辺の集合を $S$ とすると,

$$f(i) = \max_{j \in S} f(j) + c(j,i)$$

となる. $c(i, j)$ は $i$ から $j$ までの作業時間である.

$i$ の最遅結合点時刻 $l(i)$ は $i$ から出る辺の集合を $T$ とすると,

$$l(i) = \min_{j \in S} l(j) - c(i,j)$$

となる. ただし, $l(N-1) = f(N-1)$ である.

いずれもグラフをトポロジカルソートして, 最早結合点時刻は前から, 最遅結合点時刻は後ろから計算すればいい.

クリティカルパス上にいないのべ人数は, $f(i) \neq l(i)$ となる点の数である.