quadPAT图论是一大考点,主要集中在图遍历(DFS,BFS,连通分量)和最短路两个部分,还有一些图的新定义题(欧拉回路,哈密尔顿圈之类的),这类题很简单。但图最短路有些题较为复杂,需要较强的编码功底。
1、图遍历和连通分量
| 编号 | 标题 | 题解 | 难度等级 | 备注 |
|---|---|---|---|---|
| 1013 | Battle Over Cities (25) | C++题解 | 2 | 图连通分量计数 |
| 1021 | Deepest Root (25) | C++题解 | 3 | 树的最大深度 |
| 1034 | Head of a Gang (30) | C++题解 | 4 | 图遍历 |
| 1076 | Forwards on Weibo (30) | C++题解 | 2 | 图的BFS |
2、最短路径
quad图的最短路径是常考题,在PAT里面属于最后一二题位置,难度较高。我对两种常见的最短路算法
- 优先队列优化的Dijistra,无负权的情况下使用,O(n+m)log(n)O(n+m)log(n)O(n+m)log(n)
- SPFA,有负权情况下使用,O(kE)O(kE)O(kE),k一般小于2,但可通过构造数据卡成O(VE)O(VE)O(VE)
quadPAT对时间复杂度要求很低,无需优化即可通过,甚至Floyd都能过,所以题解中我统一使用优先队列优化的Dijistra,万一PAT下次卡时间了呢。
quad我在博客中对这两种最短路算法进行了解释并给出了模板,欢迎点击查看。
| 编号 | 标题 | 题解 | 难度等级 | 备注 |
|---|---|---|---|---|
| 1003 | Emergency (25) | C++题解 | 3 | 最短路径+其他变量的更新(第二标尺) |
| 1018 | Public Bike Management (30) | C++题解 | 4 | 最短路径+DFS |
| 1030 | Travel Plan (30) | C++题解 | 3 | 最短路径+其他变量的更新(第二标尺) |
| 1072 | Gas Station (30) | C++题解 | 3 | 多个点的最短路 |
| 1087 | All Roads Lead to Rome (30) | C++题解 | 4 | 最短路径+三个标尺层层更新 |
| 1111 | Online Map (30) | C++题解 | 3 | 最短路径+两个尺度 |










