【学习记录】24.02.15 图论

· · 个人记录

图论

最短路

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] 紧急集合 / 聚会

#### 加强版 建虚树，后边没咋听懂。 ## 生成树 ### P4180 [BJWC2010] 严格次小生成树 最小生成树上 倍增求LCA和路径最值。 ### CF1416D Graph and Queries 没听。 ## 拓扑排序 ### P7831 [CCO2021] Travelling Merchant 类似于反图拓扑排序，没太听懂。 ## 差分约束 ### P7624 [AHOI2021初中组] 地铁 环上差分约束，需要分类讨论。