图论-拓扑排序-应用

图论-拓扑排序-应用

AOE网

结点为事件,弧表示活动,权表示活动持续时间

用途:估算工程完成时间,找出影响工程进度的关键活动

源点:表示整个工程的开始点,也称起点(入度为0)

汇点:表示整个工程的结束点,也称收点(出度为0)

正常情况下,AOE网仅有一个源点,一个汇点。

关键路径:从源点到汇点路径长度(弧上的权值之和)最长的路径,其长度代表完成工程的最短时间。

事件的最早发生时间,活动的最早/最迟开始时间

事件的最早发生时间ve(i):

从源点到结点i的最长路径长度,它决定了所有以vi为尾的弧所代表的活动aj的最早开始时间e(j)。显然,e(j)=ve(i)。

活动的最迟开始时间l(j):

在不影响整个工程的如期完工前提下,活动aj最迟必须开始进行的时间。

。(好懒,不想写了......

求ve(i) ,vl(i)的递推公式

从ve(0)=0开始,按拓扑序向前递推

  ve(j)=max(ve(i)+dut(<i,j>))

      dp[v]=max(dp[v],dp[u]+w(u,v) )

从vl(n-1)=ve(n-1)起,按逆拓扑序向后递推:

  vl(i)=min(vl(j)-dut(<i,j>))

建反图就是:

  dp[v]=min(dp[v],dp[u]-w(u,v) )

拓扑排序跑一遍...

 

 

 

 

 

原文地址:https://www.cnblogs.com/sweetlittlebaby/p/12827698.html