PAT图论刷题总结

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

27

quadPAT图论是一大考点,主要集中在图遍历(DFS,BFS,连通分量)和最短路两个部分,还有一些图的新定义题(欧拉回路,哈密尔顿圈之类的),这类题很简单。但图最短路有些题较为复杂,需要较强的编码功底。

1、图遍历和连通分量

编号标题题解难度等级备注
1013Battle Over Cities (25)C++题解2图连通分量计数
1021Deepest Root (25)C++题解3树的最大深度
1034Head of a Gang (30)C++题解4图遍历
1076Forwards 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我在博客中对这两种最短路算法进行了解释并给出了模板,欢迎点击查看。

编号标题题解难度等级备注
1003Emergency (25)C++题解3最短路径+其他变量的更新(第二标尺)
1018Public Bike Management (30)C++题解4最短路径+DFS
1030Travel Plan (30)C++题解3最短路径+其他变量的更新(第二标尺)
1072Gas Station (30)C++题解3多个点的最短路
1087All Roads Lead to Rome (30)C++题解4最短路径+三个标尺层层更新
1111Online Map (30)C++题解3最短路径+两个尺度