图论

0.有感而发

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

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

1. 基本算法

$Case\ 1:$ Dijkstra

$~~~~~~~~$ 本质是 $贪心+DP$ 。

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

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

$Case\ 2:$ Floyd

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

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

$~~~~~~~~$ 下面对最小环进行说明:

//g[i][j]表示 i->j 的最短路,f[i][j]表示i->j的 边的长度
//把最短路拆成 (i-j) + (i>k,k->j)
//用 dji 可以做到 O(m(n+m)log m)
for(int k=1;k<=n;k++)
{
    for(int i=1;i<=k-1;i++)
        for(int j=i+1;j<=k-1;j++)
            ans=min(ans,f[i][k]+f[k][j]+g[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
            g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
}

$Case\ 3:$ Bellman–Ford

$~~~~~~~~$ 从边的角度考虑最短路：

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

$~~~~~~~~$ 如果边数大于了 n-1 , 说明原图上有负环。

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

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

$Case\ 4:$ SPFA

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

$~~~~~~~~$ 优化点这儿。

2. 常见思路

$Case\ 1:$ 分层图最短路.link.

$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$

卡 $O(m\log m)$ 的 dji 的题目少的很，遇见就要珍惜。

考虑异或性质：

x \oplus z=(x\oplus y) \oplus (y\oplus z)<=x\oplus y+y\oplus z

对于每个节点，拆成 32 个节点: $\{v|v=x \oplus2^k,k\in N,v\leq n\}$ ，边数就会缩短成 $n\log n+m$ 。

2. 神秘力量

先对补图进行概念阐述：

$~~~~~~~~$ 完全图-现有图=现有图的补图

因为dji的堆顶是所有未确定最短路里最小的，所以能用模法就用模法。

维护时可以用堆乱搞或用链表维护。分别为 $O(m \log m)$ 和 $O(n)$ 。

3. 奇怪的最短路

考虑答案长啥样：

$ans=min\left\{ dis_{特殊点1\rightarrow u}+w(u,v)+dis_{v\rightarrow 特殊点2}~~ |~~[u,v] \in G \right\}$ .

因为当前点可能存在多个前驱，所以要记录个数进行匹配。

其实还有一种方法很妙：

$~~~~~~~~$ 若要将 $n$ 个数中每两个数都产生一次配对，可以在 $log_n$ 次内用二进制思想完成。

$~~~~~~~~$ 对每一位分组：

$~~~~~~~~~~~~~~$ 0 为一组， 1 又为一组

4. 果国的奇妙旅行

首先说明最优策略是啥：通过当前道路能使答案更优。

然后说明一件事： 期望为什么要倒着求？

$~~~~~~~~$ 其实可以顺着求，但是情况不多。

$~~~~~~~~$ 主要原因是：

$~~~~~~~~~~~~~~$ 期望的递归出口是终点 $\rightarrow$ 终点 = 0 ，所以倒推。（或者把未知数砍了解方程）。

$~~~~~~~~~~~~~~$ 概率的起点是起点。

$~~~~~~~~$ 设 $f_i~:~i到n的期望步数$ ，则有

f[u]-\frac{du[u]-pt[u]}{du[u]} \times f[u]= \sum_{u\rightarrow v} \frac {f[v]}{du[u]}+1 \\ \\ 进而 ~~~f[u]=\frac{du[u]+\sum_{u\rightarrow v} {f[v]}} {pt[u]}

5.红灯

明显让你建图，但是你就是会建错。

评价：代码力。

6.CF938D

一到很像树形 $DP$ 的题。

把超级原点到每一个节点的距离设为点权即可。

5. 总结

图论很神奇，但无非就是建图和模板。

最常见的建图是分层图，也有线段树优化建图等。

简单的图论一眼题，复杂的根本想不到。

最短路 + 拓扑很常见。

图论总结

图论