图论

$0.$有感而发

​ 眼睛瞎了有利于打Dijkstra。 by NotDeep

​ 如果这题我不会做，那么一定是图论。 by NotDeep

$1.$ 基本算法

​ $Case\ 1:$ Dijkstra

​ 本质是 $贪心\ +\ DP$。

​ 适用于非负权权图，保证当前取出的节点的最短路是确定的，是未确定最短路的节点中最小的。

​ 常见题型 ： 补图，非负权图上用 ta ( $SPFA$已死 )。

​ $Case\ 2:$ Floyd

​ 通过 $O(n^3)$ 的时间求出任意两点的最短路。可以在负权图上使用。

​ 可以求 最小环,传递闭包。

​ $Case\ 3:$ Bellman–Ford

​ 从 边 的角度考虑最短路：

​ 最短路的边的个数 最多 是 n-1。

​ 通过 $for(i=1\ \rightarrow\ n)\ \ \ for([u,v] \in E)\ \ 松弛$ 可以让每一条边都走过。

​ 但实际上跑不满，所以有了 $SPFA$。

​ $Case\ 4:$ SPFA

​ 对$Case\ 3$的广搜优化，可以判负环。最坏 $O(nm)$。

​ 优化点这儿。

$2.$ 常见例题

​ $Case\ 1:$ 分层图最短路

​ $Case\ 2:$ Bellman–Ford 找负环

​ $Case\ 3:$ 跑完最短路后，在 最短路图(DAG) 上$DP$。

​ $Case\ 4:$ 多维最短路

​ $Case\ 5:$ 拆贡献/拆来源/YY长啥样

$3.$ 魔改将至

​ $Case\ 1:$ 贪心

​ 以$摄像头问题2$为例：

​ 对于一段区间 $[l,r]$ 我们连接一条 $l \rightarrow r+1$ 的边，在连接 $i \rightarrow i-1\ ,i\in n$ 。

​ 令 $dist_i$ 表示覆盖区间 $[1,i-1]$ 的代价，再跑最短路即可。

​ $Case\ 2:$ $DP$

​ 以 Wi-Fi 为例：

​ 我们把每种操作转换为 区间覆盖 ， 就转回了 $摄像头2$。

$4.$ 题目详解

$1.$ $P4366$