FLOYD 算法笔记
1. 作用
Floyd 用来求：
> 任意两点之间的最短路
适合：
* 点数比较少
* 需要求所有点对之间的最短距离
* 可以处理负边
* 但不能有负环
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 核心思想
假设现在考虑点 k 能不能作为中转点。
原本：
经过 k：
所以比较：
和
取更小的：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 三维 DP 理解
原始状态：
表示：
> 只允许 1~k 作为中间点时，i -> j 的最短距离。
转移：
也就是：
因为只需要上一层，所以可以压缩成二维数组 d[i][j]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 初始化
自己到自己：
其他点一开始不可达：
有边：
注意有重边，所以要取最小值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. FLOYD 模板
循环顺序必须是：
其中 k 表示当前允许使用的中转点。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 为什么能判断负环
正常情况下：
如果 Floyd 跑完后：
说明从 i 出发绕一圈回到 i，总权值是负数。
所以存在负环：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 小例子
有：
原来：
当 k=2 时：
所以：
得到：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 复杂度
时间复杂度：
空间复杂度：
所以 Floyd 一般适用于：
左右的图。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一句话记忆
> Floyd 就是不断枚举中转点 k，判断 i -> k -> j 会不会比原来的 i -> j 更短。
核心代码只有一句：
FLOYD算法
判断负环
BELLMAN-FORD
邮递员送信
dijkstra笔记
DIJKSTRA 朴素版本
DIJKSTRA 堆优化 MLOGN
上午挑战题
并查集笔记
1. 并查集是干什么的？
并查集主要解决两类问题：
* 合并两个集合
* 判断两个点是否属于同一个集合
常见题型：
> 有 nnn 个点，一开始互不相连。
> 不断进行“连边”和“询问两点是否连通”的操作。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 核心数组 FA[]
含义：
一开始每个点自己就是一个集合：
例如有 5 个点：
也就是：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 找集合的老大 FIND
find(x)：
> 找到 xxx 所在集合的根节点（老大）。
例如：
此时：
所以：
会一直向上找：
最终得到：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 路径压缩
这一句非常重要：
原来：
执行：
之后会变成：
也就是以后再找根节点，可以直接找到 444。
这叫：
> 路径压缩
作用：让后面的查询非常快。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 合并两个集合
先找到两个点的老大：
然后：
意思就是：
> 让 xxx 的老大认 yyy 的老大当父亲。
例如：
假设：
执行：
得到：
它们就变成同一个集合了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 判断是否在同一个集合
核心思想：
> 两个点的老大相同，就属于同一个集合。
例如：
那么：
所以 111 和 222 连通。
但是：
所以 111 和 444 不连通。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 小例子
初始：
执行：
合并 1,21,21,2：
再执行：
合并 2,32,32,3：
询问：
因为：
所以输出：
询问：
因为：
所以输出：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 模板
9. 记忆口诀
并查集最核心就三步：
有路径压缩后，单次操作可以近似看成 O(1)O(1)O(1)，mmm 次操作总体近似 O(m)O(m)O(m)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最小生成树 KRUSKAL
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
