AcWing算法提高课思路速查：图论
| 题目 | 模板 | 思路 |
|---|---|---|
| 1129. 热浪 | 单源最短路的建图方式 | dijkstra |
| 1128. 信使 | 单源最短路的建图方式 | 最大最短路 |
| 1127. 香甜的黄油 | 单源最短路的建图方式 | n次dijkstra+特判 |
| 1126. 最小花费 | 单源最短路的建图方式 | 数学等价变换 |
| 920. 最优乘车 | 单源最短路的建图方式 | 传递闭包 |
| 903. 昂贵的聘礼 | 单源最短路的建图方式 | 枚举范围 |
| 1135. 新年好 | 单源最短路的综合应用 | 预处理+全排列 |
| 340. 通信线路 | 单源最短路的综合应用 | 二分+特判 |
| 342. 道路与航线 | 单源最短路的综合应用 | 拓扑序套SPFA |
| 341. 最优贸易 | 单源最短路的综合应用 | 集合划分 |
| 1137. 选择最佳线路 | 单源最短路的扩展应用 | 虚拟源点 |
| 1131. 拯救大兵瑞恩 | 单源最短路的扩展应用 | 压位 |
| 1134. 最短路计数 | 单源最短路的扩展应用 | SPFA/dijkstra |
| 383. 观光 | 单源最短路的扩展应用 | dijkstra次短路/DP |
| 1125. 牛的旅行 | Floyd算法 | floyd |
| 343. 排序 | Floyd算法 | 传递闭包 |
| 344. 观光之旅 | Floyd算法 | 划分集合 |
| 345. 牛站 | Floyd算法 | ？？？ |
| 1140. 最短网络 | 最小生成树 | kruskal |
| 1141. 局域网 | 最小生成树 | 逆向思维 |
| 1142. 繁忙的都市 | 最小生成树 | kruscal |
| 1143. 联络员 | 最小生成树 | 缩点 |
| 1144. 连接格点 | 最小生成树 | 贪心 |
| 1146. 新的开始 | 最小生成树的扩展应用 | 虚拟源点 |
| 1145. 北极通讯网络 | 最小生成树的扩展应用 | 贪心 |
| 346. 走廊泼水节 | 最小生成树的扩展应用 | 分类讨论 |
| 1148. 秘密的牛奶运输 | 最小生成树的扩展应用 | 调整法 |
| 904. 虫洞 | 负环 | SPFA |
| 361. 观光奶牛 | 负环 | 01分数规划 |
| 1165. 单词环 | 负环 | 神奇建边 |
| 1169. 糖果 | 差分约束 | 模板 |
| 362. 区间 | 差分约束 | 前缀和 |
| 1170. 排队布局 | 差分约束 | 判断连通性 |
| 393. 雇佣收银员 | 差分约束 | 前缀和+枚举/二分 |
| 1172. 祖孙询问 | 最近公共祖先 | 倍增 |
| 1171. 距离 | 最近公共祖先 | tarjan |
| 356. 次小生成树 | 最近公共祖先 | 1148.LCA优化 |
| 352. 闇の連鎖 | 最近公共祖先 | 树上差分 |
| 1174. 受欢迎的牛 | 有向图的强连通分量 | 缩点+叶节点 |
| 367. 学校网络 | 有向图的强连通分量 | max(根，叶) |
| 1175. 最大半连通子图 | 有向图的强连通分量 | 缩点+判重+直径 |
| 368. 银河 | 有向图的强连通分量 | 缩点+拓扑序DP |
| 395. 冗余路径 | 无向图的双连通分量 | ceiling(leaves/2) |
| 1183. 电力 | 无向图的双连通分量 | 从割点入手 |
| 396. 矿场搭建 | 无向图的双连通分量 | 分类讨论 |
| 257. 关押罪犯 | 二分图 | 二分+二分图判定 |
| 372. 棋盘覆盖 | 二分图 | 染色 |
| 376. 机器任务 | 二分图 | 最小点覆盖 |
| 378. 骑士放置 | 二分图 | 最大独立集 |
| 379. 捉迷藏 | 二分图 | 最小路径重复点覆盖 |
| 1123. 铲雪车 | 欧拉回路和欧拉路径 | 欧拉回路 |
| 1184. 欧拉回路 | 欧拉回路和欧拉路径 | 删边优化 |
| 1124. 骑马修栅栏 | 欧拉回路和欧拉路径 | 按边从小到大 |
| 1185. 单词游戏 | 欧拉回路和欧拉路径 | 建边 |
| 1191. 家谱树 | 拓扑排序 | 模板 |
| 1192. 奖金 | 拓扑排序 | 342.简化版 |
| 164. 可达性统计 | 拓扑排序 | 逆拓扑+压位 |
| 456. 车站分级 | 拓扑排序 | 虚拟中介 |