数据结构专题：图论在408第一季的应用与实践 III

关键路径

改名了

最长的路径是关键路径，在关键路径上的是关键活动

还有什么最早最晚开始时间，这不是我们软件工程的题目吗，下次记得表明出处

怎么做

这个简单看看，后面有具体题目

第一步

先求最早发生时间Ve

这里怎么求，我拿V4举例

V4这里可以看见啊，想要嗯造V4，你就得V2和V3这个大前提整完，都给整完了才能V4，所以我们找最大的，也就是2+4这条边

然后后面就这样求求得了

第二步

这里求最晚发生时间Vi

这里就倒着算

拿V3举例啊，兄弟们

V3这里有2条出度，到底是V4的6 – 4，还是V6的8 – 3 呢

如果我们选5天的话，这里V3到V4已经是第9天了，再到V6都11天了，V6都白等3天了，不能整

所以这次我们选最小的

选2天的，即6-4 =2 

第三步

最早开始时间ei 明面上写着呢

最晚开始时间li 就是拿最晚结束时间 – 做的时间 = 最晚开始时间

为什么不选b呢，因为我们是求所以弧的最晚开始时间，别想到其他的地方了

然后我们把 li – ei 就可以得到 我们可以爽几天后再去工作

最后一步

然后找为0的，也就是一点不能歇的，就是关键路径

题目

1

b

2

第一问

12  a e m n

工程的最短完成时间 = 关键路径长度（可以这么理解：直到耗时最长的那个任务完成了，工程才能完成）

第二问

事件1：开始干活了兄弟们，b你要干五天哦（还剩5天！），a你要干两天哦（还剩2天！），d你要干三天哦（还剩3天！）

a：我日尼玛，给老子累坏了，2天过去终于干完了，到你干活了e（还剩3天！），还有c（还剩1天！）

e：哈哈哈，题目问我和我一起干活的还有谁，我瞅瞅，b有个（还剩3天！）d有个（还剩1天！），c也有个（还剩1天！）

bdc

第三问

j 6

第四问

活动b在时刻6开始

但活动b最晚也要时刻5开始，很显然耽搁了一天

现在，活动b要从时刻6开始了，也就是说，事件2会变成6+5=11天了，k要变成1才能保证工程不延期，但k活动事件改变了，不符合题意，所以得把b的持续时间改成4天一切才安好。

然后第二个不改变b的持续时间，也就是从第6天开始 + 5天的持续时间=11天，然后事件2就会变成11/11，事件5变成13/13，很显然延误了1天，想回到原来的12/12并且不改b的持续时间，可以把活动k的2改成1，这样就不会延期了，还是12/12

作者：-qOVOp-