能力提升综合题单Part8 图论

## Part 8 图论 > 图论是数学的一个分支，它以图为研究的对象。 ### Part 8.1 图的存储与遍历 > 这里的图论内容都比较简单，涉及图的存储以及遍历图的方式。 - [P2661 信息传递](https://www.luogu.com.cn/problem/P2661) - [P2921 [USACO08DEC]Trick or Treat on the Farm](https://www.luogu.com.cn/problem/P2921) ### Part 8.2 最短路问题 > 很多题目都可以转化为最短路的模型。因此，掌握最短路算法非常重要。 - [P3371 【模板】单源最短路径（弱化版）](https://www.luogu.com.cn/problem/P3371) - [P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779) - [P5905 【模板】Johnson 全源最短路](https://www.luogu.com.cn/problem/P5905) - [P1144 最短路计数](https://www.luogu.com.cn/problem/P1144) - [P1462 通往奥格瑞玛的道路](https://www.luogu.com.cn/problem/P1462) - [P1522 Cow Tours](https://www.luogu.com.cn/problem/P1522) - [P1266 速度限制](https://www.luogu.com.cn/problem/P1266) - [P4001 [ICPC-Beijing 2006]狼抓兔子](https://www.luogu.com.cn/problem/P4001) - [P4568 [JLOI2011]飞行路线](https://www.luogu.com.cn/problem/P4568) - [P5304 [GXOI/GZOI2019]旅行者](https://www.luogu.com.cn/problem/P5304) - [CF1163F Indecisive Taxi Fee](https://www.luogu.com.cn/problem/CF1163F) ### Part 8.3 树上问题 > 作为一种特殊的图，树上的问题具有很多鲜明的特点。 #### Part 8.3.1 二叉树 > 二叉树是一种特殊的树，它有很多特殊的性质。 > - [P1087 FBI树](https://www.luogu.com.cn/problem/P1087) - [P1030 求先序排列](https://www.luogu.com.cn/problem/P1030) - [P1305 新二叉树](https://www.luogu.com.cn/problem/P1305) - [P1229 遍历问题](https://www.luogu.com.cn/problem/P1229) - [P5018 对称二叉树](https://www.luogu.com.cn/problem/P5018) - [P5597 【XR-4】复读](https://www.luogu.com.cn/problem/P5597) #### Part 8.3.2 树的直径 > 树的直径被定义为树上最远的两点间的距离。 > > 计算树的直径，可以通过两遍 DFS 解决。 - [P2195 HXY造公园](https://www.luogu.com.cn/problem/P2195) - [P3629 [APIO2010]巡逻](https://www.luogu.com.cn/problem/P3629) - [P5536 【XR-3】核心城市](https://www.luogu.com.cn/problem/P5536) - [P1099 树网的核](https://www.luogu.com.cn/problem/P1099) - [P4408 [NOI2003]逃学的小孩](https://www.luogu.com.cn/problem/P4408) #### Part 8.3.3 最近公共祖先 > 两个点的最近公共祖先，即两个点的所有公共祖先中，离根节点最远的一个节点。 > > 求解最近公共祖先，常用的方法是树上倍增或者树链剖分。 - [P3379 【模板】最近公共祖先（LCA）](https://www.luogu.com.cn/problem/P3379) - [P3938 斐波那契](https://www.luogu.com.cn/problem/P3938) - [P4281 [AHOI2008]紧急集合 / 聚会](https://www.luogu.com.cn/problem/P4281) ### Part 8.4 生成树 > 用 $ n-1 $ 条边将图上的 $ n $ 个点连接起来，形成的树就被称为生成树。 - [P3366 【模板】最小生成树](https://www.luogu.com.cn/problem/P3366) - [P4180 【模板】严格次小生成树[BJWC2010]](https://www.luogu.com.cn/problem/P4180) - [P2872 [USACO07DEC]Building Roads](https://www.luogu.com.cn/problem/P2872) - [P1991 无线通讯网](https://www.luogu.com.cn/problem/P1991) - [P1967 货车运输](https://www.luogu.com.cn/problem/P1967) - [P4047 [JSOI2010]部落划分](https://www.luogu.com.cn/problem/P4047) ### Part 8.5 拓扑排序 > 将一个有向无环图排序，使得所有排在前面的节点不能依赖于排在后面的节点，这就是拓扑排序。 - [P1113 杂务](https://www.luogu.com.cn/problem/P1113) - [P1983 车站分级](https://www.luogu.com.cn/problem/P1983) - [P1038 神经网络](https://www.luogu.com.cn/problem/P1038) ### Part 8.6 差分约束 > 差分约束要解决的问题是：求出一组 $ n $ 元不等式的一组解，使得所有约束关系都能得到满足。 - [P5960 【模板】差分约束算法](https://www.luogu.com.cn/problem/P5960) - [P3275 [SCOI2011]糖果](https://www.luogu.com.cn/problem/P3275) - [P2294 [HNOI2005]狡猾的商人](https://www.luogu.com.cn/problem/P2294) - [P4926 [1007]倍杀测量者](https://www.luogu.com.cn/problem/P4926) - [P5590 赛车游戏](https://www.luogu.com.cn/problem/P5590)