竞赛算法与算法训练 · 小纸条

选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。

第 1 章7 第 2 章7 第 3 章7 第 4 章7 第 5 章7 第 6 章7 第 7 章7 第 8 章7 第 9 章7 第 10 章7 第 11 章7 第 12 章7

只印题目

第 1 页 · 正面（题目）

1松弛与最短路上界

闭卷重建松弛与最短路上界的对象、状态、事件、不变量与一个失败反例。

2Dijkstra与堆优化

闭卷重建Dijkstra与堆优化的对象、状态、事件、不变量与一个失败反例。

3Bellman-Ford与负环

闭卷重建Bellman-Ford与负环的对象、状态、事件、不变量与一个失败反例。

4Floyd与全源最短路

闭卷重建Floyd与全源最短路的对象、状态、事件、不变量与一个失败反例。

5Kruskal与割性质

闭卷重建Kruskal与割性质的对象、状态、事件、不变量与一个失败反例。

6Prim与跨割最轻边

闭卷重建Prim与跨割最轻边的对象、状态、事件、不变量与一个失败反例。

7最短路和MST的反例对照

闭卷重建最短路和MST的反例对照的对象、状态、事件、不变量与一个失败反例。

第 1 页 · 背面（答案）

核心机制：围绕Dijkstra与堆优化先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成Dijkstra与堆优化的暴力、优化、对拍与复盘；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕松弛与最短路上界先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成松弛与最短路上界的暴力、优化、对拍与复盘；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕Floyd与全源最短路先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成Floyd与全源最短路的暴力、优化、对拍与复盘；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕Bellman-Ford与负环先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成Bellman-Ford与负环的暴力、优化、对拍与复盘；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕Prim与跨割最轻边先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成Prim与跨割最轻边的暴力、优化、对拍与复盘；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕Kruskal与割性质先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成Kruskal与割性质的暴力、优化、对拍与复盘；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。本课必须再检查边界输入、整数溢出、下标和不可行状态。。

核心机制：围绕最短路和MST的反例对照先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；实验入口：完成最短路和MST的反例对照的暴力、优化、对拍与复盘；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。本课必须再检查边界输入、整数溢出、下标和不可行状态。。