图论专题二

第二讲

（17分11秒开始有声音）

1. dijkstra+heap

2. bellman-ford

3. SPFA算法

4. 判断负环

方法1：最短路经过边数不能大于n-1（推荐）

方法2：SPFA任何一个点入队次数不能超过n次

5. 差分约束

6. PPT 17页 problem2 （差分约束 HDU3592）

7. PPT 18页 problem3 （查分约束 HDU3666）

8. 树上序列

9. 最近公共祖先（LCA）

课程中涉及的题目：

HDU3592: World Exhibition

HDU3666: THE MATRIX PROBLEM