《算法竞赛进阶指南》第一版勘误详情

"《算法竞赛进阶指南》第一版（2018年1月第一次印刷）的勘误，包含了重要勘误和一般勘误，主要涉及算法相关内容，如二分法、三分法、约数问题、有向图的强连通分量、二分图的匹配以及网络流的最大流问题。" 这篇摘要详细列举了《算法竞赛进阶指南》一书中的若干错误，主要集中在算法的解释和应用上。首先，关于【二分法】的修正，书中提到了单峰函数的三分法寻找极大值点的问题。若在三分过程中，\( f(lmid) < f(rmid) \)，极大值点应在\( lmid \)的右侧，此时可以将左边界设为\( lmid \)；反之，若\( f(lmid) > f(rmid) \)，极大值点位于\( rmid \)的左侧，右边界应设为\( rmid \)。然而，如果函数不严格单调，在相等值区域存在的情况下，三分法不再适用。 其次，关于【约数问题】，书中给出了解题方法，特别是针对Hankson的趣味题，列出了不同情况下\( mx \)的取法，如\( ma > mc, mb < md \)时，\( mx \)唯一取\( mc=md \)，等等，这有助于理解如何根据给定条件确定变量的值。 接着，涉及到【有向图的强连通分量】，在Tarjan算法的应用中，修复了计算low值的语句，正确做法是将low[x]更新为dfn[ver[i]]和low[x]的最小值。 在【二分图的匹配】部分，书中指出如果在判定无向图是否为二分图时，发现节点v[y]的颜色与当前颜色color相同，那么图不是二分图，并终止算法。 最后，对于【最大流】问题，书中建议在原二分图的边容量都设置为1，然后求解最大流，这是求解二分图最大匹配的一种常见方法。 一般勘误部分提到了【位运算】表格的排版错误，将unsigned int和int的位置进行了纠正。 这些勘误修正对于理解和应用相关算法至关重要，尤其是对于参与算法竞赛或深入学习算法的读者，确保对算法的正确理解和使用是非常重要的。