图论进阶算法知识点整合

倍增Floyd

解决k步最短路问题

LCA

树上最近公共祖先，有多种求法
1.倍增
2.树链剖分
3.tarjan离线求法
4.dfs序RMQ求法
常用于解决树上路径问题，若边权为1，length(u->v)=depth(u)+depth(v)-2*depth(lca(u,v));
倍增法可维护树上路径最值问题。

树链剖分

可以将一棵树变为一个序列，类似DFS序，分为重链剖分和长链剖分，可以证明两点间路径在生成的序列上至多分为$logn$段，从而可以用线段树维护，树上路径权值和，树上子树权值和，树上点权修改，树上权最值，LCA等问题。复杂度为$O(logn{)}^2$

Kruskal重构树

可以解决图上任意两点路径上最小（大）边权。建立Kruskal重构树，求出两点LCA的权值即为答案。

最小割树

解决任意两点间最小割问题。生成最小割树，问题转变为树上路径最小值，可以用树链剖分或LCA倍增来解决。

圆方树

将无向图变为一棵树。
可以解决
1.两点之间路径必经点的个数。
2.求不一定连通的简单无向图中，满足「存在一条路径 s→f 经过 c 」的 ⟨s,c,f⟩ 的个数。⟨s,c,f⟩ 和 ⟨f,c,s⟩ 算不同的元组。

最小树形图（朱刘算法）

生成树边权值和最小