0%

【习题解答】 题解勘误

8.28

第六问的复杂度和正确性部分,把第三行的图中“每个顶点,其能到达的顶点都是标记的”改完“每个标记的顶点,其能到达的顶点都是标记的”

9.11

对于书上的109页算法,一方面要修改第3行的判断条件;另一方面在第7-10行关于邻点的处理完成后还要再进行非邻点的处理。复杂度是O(V^2)的。

12.2

“每次选择与“最短路径树”相邻的且capcity值最小的点”改为“每次选择与“最短路径树”相邻的且capcity值最大的点”

20.5

  • 本题使用q算法解决p问题,注意到p随着调用的嵌套是一个变动的值;q是一个固定值,因为q是算法是已知算法
  • 如果删除至还剩余k个元素,且k小于q时,此时q算法无法被调用。但此时还需要的固定代价额外处理即可

21.5

第2问状态转移方程改成

勘误致谢(字母序):ljw、枸杞(匿名群昵称)、zyb、zjj、zzh