下面关于求关键路径的说法不正确的是()。
这道题简直是中的,中的,简直是数据结构题中的糟粕.是我至今遇到过最没有意思的文字游戏题.哪怕他定义一下箭头的弧头弧尾是什么,都不会出现这么多争议.
首先箭头的箭头部分应该是这道题意味的弧头,所以另一边是弧尾.
定义一个所有与k相邻的点对<ui,k,vj>,点对的边作为活动
那么对于B来说,B是对的.k的最早开始时间,是min{<k,vj>活动的最早开始时间},所以是所有的活动的最小值,那你发现所有活动的始边都是k,所以他们的最早开始时间是一样的,因为都是由k递推得来的.同时也是max(<ui,k>最早开始时间+活动权值),也就是所有<ui,k>活动的最晚结束时间.
那么对于C来说,他就是错的.k的最晚开始时间是min{vj的最晚开始时间-对应的活动权值},同时也是min(<k,vj>的最晚开始时间).同时也是min{<ui,k>的最晚结束时间},那你此时会发现所有<ui,k>的最晚结束时间是一样的.因为是由k倒推得来的