整齐心情

文章
10
资源
0
加入时间
2年10月17天

练习30,图论 P1113 杂务【拓扑排序/邻接表】

P1113 杂务 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)思路:一开始只是将所有入度为0的点加入队列,并且 dp[i]=len[i] (表示没有前驱杂务的杂务完成时间就等于它的耗时),然后遍历这些杂务的出边并且将出边对应的点入度-1。如果有点的入度减至0则代表它所有的前驱杂务完成时间已经计算好,此时该点的完成时间等于前驱杂物完成时间的最大值+当前杂物的耗时,即 dp[i]=max(dp[prei])+len[i] ,如此循环直到遍历完所有点,所以结果就是所有杂务完成时间的