本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-15 17:12:33

图论

最短路

CF715B Complete The Graph

二分或Dij思想填数。

P2149 [SDOI2009] Elaxia的路线

Dij预处理+DAG拓扑排序。

P5304 [GXOI/GZOI2019] 旅行者

二进制分组建虚点+Dij。

P2371 [国家集训队] 墨墨的等式

同余最短路。

CF786B Legacy

线段树优化建图 Dij。

P4001 [ICPC-Beijing 2006] 狼抓兔子

虚点建图最短路/最大流最小割。

CF1163F Indecisive Taxi Fee

黑题放弃...

学长讲了思路，分类讨论+Dij处理三种+线段树优化处理最后一种，最后一种不太明白。

LCA

P3398 仓鼠找 sugar

LCA+判断是否在路径上。

P4281 [AHOI2008] 紧急集合 / 聚会

$3$ 次LCA，推出答案为较深点，再求解。

加强版

建虚树，后边没咋听懂。

生成树

P4180 [BJWC2010] 严格次小生成树

最小生成树上 倍增求LCA和路径最值。

CF1416D Graph and Queries

没听。

拓扑排序

P7831 [CCO2021] Travelling Merchant

类似于反图拓扑排序，没太听懂。

差分约束

P7624 [AHOI2021初中组] 地铁

环上差分约束，需要分类讨论。