图论-专题一（中招）

第一讲

（10分2秒开始有声音）

1. 图论基础知识

2. 没有上司的舞会——章鱼图版（38分左右）

附赠一题：P2607 [ZJOI2008] 骑士

3. 仙人掌图（1小时7分左右）

  3.1 边仙人掌

  3.2 点仙人掌

4. DAG有向无环图 —— 一般都与DP有关

5.二分图 ps.树一定是二分图

6.图的存储

  6.1 邻接矩阵

  6.2 链式前向星（邻接表，又称边表）

7. 没有上司的舞会（章鱼图）代码

8. 最短路问题

  8.1 单源最短路

  8.2 多源最短路

9. Floyd算法

10. dijkstra算法——插播一个题 P5022 [NOIP2018 提高组] 旅行

进阶指南必做题目

1.Telephone Lines（通信线路)   acwing链接   洛谷链接

2.道路与航线（BZOJ2200）

3.Sort It all out （排序POJ1094)

4.sightseeing trip（观光之旅 POJ1734）

5.cow relays(牛站)   acwing链接   洛谷链接