图论相关

qerrj / 2024-09-25 / 原文

图论

参考

oiwiki 网上博客

树

LCA

性质

$LCA(A \cup B) = LCA(LCA(A), LCA(B))$
一堆点集的LCA 等于其中 dfn 最大的和最小的点的 LCA

dfs序求lca

好写且 $O(1)$，吊打欧拉序和倍增。

如果两个点 $x$ 和 $y$ 不存在祖孙关系，那么 $LCA(x,y) = fa(min(dfn_x, dfn_y))$。

我们钦定 $dfn_x < dfn_y$ 这里的 min() 是指 $[dfn_x, dfn_y]$ 之间深度最小的点的编号。

考虑证明很简单，思考dfn是怎么来的即可。

如果存在祖孙关系，那么 $LCA = x$，但是为了方便写，我们可以把两种情况统一起来，我们将dfn_x加一即可，这样加一之后不影响第一种情况，第二种情况的答案也可以算到。

代码：

int dfn[N], tim, st[21][N];
void dfs(int u, int pre) {
	st[0][dfn[u] = ++tim] = pre;
	for(int i = head[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if(v == pre) continue;
		dfs(v, u);
	}
}
int Min(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
void init() {
	for(int i = 1; i <= 20; i++) 
		for(int j = 1; j + (1 << i) - 1 <= n; j++) 
			st[i][j] = Min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
int lca(int x, int y) {
	if(x == y) return x;
	if((x = dfn[x]) > (y = dfn[y])) swap(x, y);
	int d = 31 ^ __builtin_clz(y - x); x++;
	return Min(st[d][x], st[d][y - (1 << d) + 1]);
}

实际实现不需要dep和fa数组，具体细节见代码。

这个做法的瓶颈在RMQ，如果用一些高科技搞RMQ可以做到 $O(n)~O(1)$，但基本常数较大且不怎么好些。

树剖求lca

$O(n)~O(logn)$ 常数小，代码也比较简单，可以替代倍增，但最好的还是dfs序。

树的直径

两种方法：两次dfs或者树形DP。推荐第二种，因为好写且支持找负边权的直径，树形DP又有两种方法，这里写一种好写的。

不过有意义的，两次dfs的结论也可以记住：

在都是非负边权的情况下，从树上任意一点 $x$ 出发，到达的最远的点 $y$ 一定是直径的一端。

具体证明很简单，使用反证法，分三种情况分别考虑

$x$ 就在直径上
$x$ 不在直径上，但是求得的路径 $(a,b)$ 与直径 $(z, w)$ 有交点。
没有交点。

DP代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, dp[N], ans;
void chmx(int &x, int y) { x = max(x, y); }
vector<int> G[N];
void dfs(int u, int fa) {
	for(int v : G[u]) if(v ^ fa) {
		dfs(v, u);
		chmx(ans, dp[u] + 1 + dp[v]);
		chmx(dp[u], 1 + dp[v]);
	}
}
int main() {
	scanf("%d", &n);
	for(int i = 1, u, v; i < n; i++)
		scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
	dfs(1, 0);
	printf("%d", ans);
	return 0;
}

动态维护直径

树的重心

性质

重心最多两个，如果有两个，那么肯定相邻。
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。（这个也是充要条件）
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。（这个性质也挺好）
要是通过一条边把两棵树连起来，那么新的重心在原来两棵树的重心的路径上。（有助于动态维护重心）
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离

动态维护树的重心

证明：先咕着。

树剖

长剖和实剖先不展开。主要就是重链剖分。
重链剖分及其擅长解决树上路径问题，他把树剖成了若干条重链，并且任意一条路径上最多 $logn$ 条重链，这使得我们可以使用一些可以维护链上信息并且支持信息快速合并的数据结构来维护重链，并且树剖利用和拓展dfs序的性质，把链搞成一个区间，使得我们的维护更加的方便。
顺带着dfs序的性质，树剖对于子树信息的维护也很擅长。
具体算法内容就不赘述了，这里只做总结。

dsu on tree

也叫树上启发式合并，有些时候我们完全可以直接启发式合并，但是这个算法给了另一种启发式合并的思路，dsu on tree主要是对子树信息统计，具体算法很人类智慧，考虑我们要统计每个点的子树信息，并且只能用一个桶或者数据结构。

比如我们dfs目前到了节点 $u$，我们会将 $u$ 的儿子 $v$ 一一递归下去，这样的话我们遍历完一个儿子就要清空桶，不然其他儿子的信息就不对，遍历完儿子之后我们再来统计 $u$ 的信息，那么就有一个人类智慧，最后一个儿子遍历完不用清空，可以留下来给 $u$ 用，这样就有了一个剪枝。再人类智慧的，我们可以钦定最后一个儿子是重儿子，这样剪枝最优。事实上，这已不仅仅是剪枝，而已经达到了 $O(nlogn)$ 的复杂度了。

考虑证明：计算每个点会被统计几次，如果他在重链上，那么他的信息会被继承上去，不会重复统计，所以说一个点的统计次数就等于这个点到根的重链数量，也就是 $O(logn)$，所以总时间复杂度 $O(nlogn)$。

虚树

虚树适用于某些题目，这些题目通常需要你做很多次树形DP，只有少部分点是我们DP需要的，我们可以根据他们的祖孙关系建出虚树，这样复杂度就降下来了。

结论1：一个集合的LCA 等于集合里dfn最大的和dfn最小的两点的LCA。

结论2：将一个集合的点按dfn排序得到 $a_1...a_n$，$LCA(a_1, a_2), LCA(a_2, a_3)...LCA(a_{n-1}, a_n)$ 中一定出现等于 $LCA(a_1, a_n)$ 的点。

我们把关键点取出来，按dfn排序，取出相邻两点的LCA，然后去重，得到的这些点根据祖孙关系建树的话一定可以连通。由结论1和结论2可以知道，任意一个区间的LCA，都会在相邻两点的LCA中出现。所以这些点一定够。

需要哪些点知道了，接下来就只需要建树，把这些点再按dfn排序，遍历这个数组，遍历所有相邻的数 $x, y$，将 $LCA(x, y)$ 连向 $y$。就做完了。

考虑证明：

如果 $x$ 与 $y$ 存在祖孙关系，那 $x$ 肯定是祖先，并且他们之间不会有其他点，$x$ 连向了 $y$。这是正确的。
如果不存在，那么就来自不同的子树，考虑 $LCA(x, y)$ 到 $y$ 的路径上肯定没有其他点，这么连也是对的。

考虑上面一共连了 $n - 1$ 条边，并且都是合法的，我们选出的点保证了他们根据祖孙关系建树一定连通，所以连出来的这么个东西就是树。

树分治

这个内容主要是题目，并且很熟了，就不写了。

点分治

边分治

点分树

树哈希

树上随机游走

矩阵树定理

拓扑排序

DAG可以DP。根据拓扑序来DP没有后效性。所以把限制看成边，把问题转化成图很关键。

最小生成树

Kruskal

这个算法人人都会吧，是个贪心算法，但是正确性还是有待证明（比如有多条边权值一样，那我选哪些，选了这些边很可能对树的形态造成影响导致后面选的不优）。所以所以这里证明一下实际上没有影响，就是能选就选：

我们现在只需要证明任意时刻，我们选的边集一定可以被某一个MST包含即可。

我们设目前选的边集为 $G$，他被这个图的一个MST $T$包含，现在我们加入一条合法的边 $e$。然后归纳证明一下

如果 $e$ 包含于 $T$，那么就显然成立。
如果不包含，那么 $e$ 在 $T$ 中一定形成了一个环，并且这个环上不可能有比他大的，不然 $e$ 就可以替换其中一条大边成为一个新的MST，这不符合定义，并且不存在未被选的比 $e$ 小的边，这个显然正确，如果存在，那么在之前就会被选，所以环上只会存在若干条和 $e$ 一样大的边，这是我们可以随便拆一条边，然后把 $e$ 放进去，设其为 $t$，那么我就令 $T - t + e$ 为新的MST。

这就引出了生成树的唯一性。

生成树的唯一性

考虑要看生成树是不是唯一，就是上面kruskal的证明过程。
具体实现就是考虑所有权值相同的颜色段，扫描到一个颜色段后，先看有多少个能放进去得到一个预估放的数量，然后一个一个放，得到实际放的数量，如果二者不相等，就说明一定有边形成了环，而且环上有权值相同且已经被选。所以就可以拿目前这个边去替换那个权值相同，根据前文的证明，替换了不会影响答案。

Boruvka

就是每个连通块同过最小边往外合并，初始时每个点为一个连通块，每一轮连通块减半，所以最多 $logn$，总合并次数 $O(nlogn)$，考虑找到最小边一般要数据结构，所以一般复杂度是 $O(nlog^2n)$ 的，这个算法很擅长解决完全图MST的问题。

关于正确性的证明暂时还不会...网上也没找到资料。

瓶颈生成树

定义：最大边在所有生成树中最小。
一般我们要求最小瓶颈生成树，但是这个我们不会求，考虑最小生成树一定是瓶颈生成树，求最小生成树就很简单了。

证明：如果一个MST $T$ 不是瓶颈生成树，那么存在一个瓶颈生成树 $G$ 中所有的边都比 $T$ 中的最大边小，所以我们可以把最大边拆了，然后拿瓶颈生成树中随便一条边把两个连通块连起来。考虑一定存在这条边，如果不存在，那就说明 $G$ 不连通，所以一定存在。

最小瓶颈路

定义：$x$ 到 $y$ 的最小瓶颈路就是一条 $x$ 到 $y$ 的路径，满足这条路径上的最大值最小。
结论：最小生成树上两点路径就是一条瓶颈路。
证明：没搜到...

kruskal重构树

原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值
这些奇妙的性质搭配数据结构就很方便。

kruskal的过程中，每次合并两个连通块时，新建一个节点，点权为边权，将两个连通块的根节点作为新点的左右儿子。

原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。

也就是两点之间最小瓶颈路就是他们的 lca 的点权。

到点 $x$ 的简单路径上最大边权的最小值 $\leq val$ 的所有点 $y$ 均在 Kruskal 重构树上的某一棵子树内，且恰好为该子树的所有叶子节点

最小斯坦纳树

最小树形图

最小直径生成树

最短路算法

Floyd

这个算法可以求全源最短路，不关无向有向，不管边权正负，但是不能有负环。

考虑 Floyd 就是 DP，我们设 $f[k][i][j]$ 是只经过 $1$ 到 $k$ 这些点， $i$ 到 $j$ 的最短路径长度。那么则有转移方程：

\[f[k][i][k] = max(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j]) \]

然后滚动数组优化一下空间。

拓展

用 Floyd 求正权无向图的最小环。

我们仍然套用Floyd的状态和方程。

考虑这肯定是一个简单环，因为是正环，构造性证明即可。然后显然我们可以把每一个简单环映射在每个简单环上的最大编号的节点，这样我们枚举最大编号的节点就可以考虑完所有的环，然后我们就要枚举最大编号的的节点 $u$ 两侧的节点 $x$ 和 $y$，显然剩下的节点直接取 $x$ 与 $y$ 之间的最短路径即可，考虑这个路径一定不经过 $u$，因为 $u$ 为最大编号的节点
。

Bellman–Ford

这个算法可以求有负边权的图的最短路，还可以判断负环。主要是基于松弛操作。我在初学最短路算法时有个最大的疑惑就是为什么松弛操作要叫做 “松弛”操作，现在知道了，本来是 relax ，考虑要满足 $d[v] \leq d[u] + edge[i].dis$，当我们进行一次松弛操作后，就离完全满足这个不等式又近了一步，慢慢的松弛直到完全满足这个不等式，就可以称为 relax，翻译为松弛。

算法：考虑最短路最长有多少条边， $n - 1$ 条边，我们每一轮松弛操作，也就是对每一条边进行松弛，最起码使所有的最短路边数增加一（否则就无法松弛，也就是已经是最短路），所以最多进行 $n - 1$ 轮，那么时间复杂度 $O(nm)$。

判断负环：考虑如果有负环，那么松弛操作就永远不会停止，所以如果 $n - 1$ 轮松弛后，还有边可以松弛操作，那么就是有负环。

需要注意的是，如果只是从 $s$ 出发，只能判断从 $s$ 出发能否到达负环，我们要判断整个图有没有负环的话，需要连一个超级源点连向所有节点，边权为 $0$。

优化

队列优化（SPFA）:
考虑人类智慧，比如第一轮松弛操作时，显然我们可以只松弛与 $s$ 相连的节点，所以只有已经被松弛过的节点才可能被优化。所以我们可以用一个队列，用来装被松驰过的节点。该算法同样可以判断负环，我们可以开个数组记录每条最短路的边数，当一条最短路的边数 $\geq n$ 时，说明进入了负环。
时间复杂度: $O(km)$

优先队列优化：
考虑人类智慧，队列中更小的放前面，可以省去一些非松弛操作，但是会带来 $logn$ 的复杂度。

双端队列优化：
考虑比对头小的就放入队头，否则放入队尾。

考虑SPFA复杂度玄学，我觉得最有用的就是 dinic 跑费用流时好用，如果想用dinic过大数据可以把各种优化都试一试。

Dijkstra

最常用的最短路算法了，可以求非负边权图的最短路，时间复杂度 $O(nlogn)$。

算法：我们定义两个集合 $S$， $T$， $S$ 为已经确定最短路的点集， $T$ 为还未确定的点集。我们每次从 $T$ 中取出路径长度最短的点加入集合 $S$，然后再对他的所有出边进行松弛。

显然，每个点遍历了他的所有出边，取出最小值可以用优先队列，时间复杂度 $O(mlogm)$。

正确性证明：很明显，我们只需要证明，每次从 $T$ 中取出最小值时，那么这个点已经确定了最短路，我们可以感性证明，如果他不是最短路，那么实际的最短路肯定先被取出来。

例题

P4568 [JLOI2011] 飞行路线

分层图，其实我更愿意用DP的思想去理解，这样更加的通用，我们设 $dp[i][j]$ 表示从 $s$ 到 $i$ 经过了 $k$ 次优惠，我们考虑转移 $dp[i][j]$ 可以向 $dp[][j + 1]$ 或者 $dp[][j]$ 转移，实际哪个点根据边来判断，再加上边权即可，然后我们可以用最短路算法帮我们跑最短路。

[ABC077D] Small Multiple

同样可以用DP的思想，我们发现是 $K$ 的整数倍，也就是 $\equiv 0 \pmod {K}$，我们发现有效状态只有 $0$ 到 $K - 1$，然后考虑转移，我们想要枚举所有的数，那么可以通过加 1，就可以枚举所有的数了， $dp[i]$ 向 $dp[(i + 1) % k]$ 转移，边权为 1，但是我们还要计算数位和，如果进位了就数位和就错了，我们可以考虑再建一种边 $dp[i]$ 向 $dp[10i % k]$ 转移，边权为 0，这样就可以避免一直加 1加到进位的情况，因为那样肯定不优。

CF786B Legacy

考虑要单点对区间，区间对单点，考虑套用线段树的结构，我们开两个线段树，然后把叶子节点之间连边权为 0 的边，这样就相当于同一个点了。

P6348 [PA2011] Journeys

考虑区间对区间，和上面的没什么区别，只是搞个虚点又可以减少边数。

P9520 [JOISC2022] 监狱

最短路树和图

考虑最短路图就是所有满足 $d[v] == d[u] + edge[i].dis$ 的边和点构成的图，最短路树就是他的一颗生成树，我们一般还要求最短路树边权和最小，可以在dijkstra的时候就建好。

CF1076D Edge Deletion

板子题

P6880 [JOI 2020 Final] 奥运公交

考虑数据范围 $N$ 很小，甚至可以 $O(n^2)$ dijkstra，然后我们可以枚举一下翻哪条边，如果不在最短路 DAG 上，那么就不影响，如果在，就会有影响，我们不知道哪一条是最短路，所以就要跑dijkstra，我们建个最短路树这样就只需要跑 $O(n)$ 次。

同余最短路

可以求出有多少数值可由给定数的系数非负线性组合得到。
一般用SPFA更快，因为建图特殊。

差分约束

差分约束问题通常有多个形如 $x_v − x_u ≤ a_i$ 的问题组成，然后判断是否有解。
差分约束的解决依赖于三角形不等式，即 $∀(u, v, w) ∈ E, dis_u + w ≥ dis_v$。
在单源最短路中，如果有边 $(u, v, w)$，那我们有 $dis_v ≤ dis_u + w(u, v)$，即 $dis_v − dis_u ≤ w(u, v)$，也就
是 $dis_u − dis_v ≥ −w(u, v)$。

P5590 赛车游戏

考虑我们要满足边权为 $[1,9]$，考虑可以用差分约束， $dis[u] + edge[i].dis \geq dis[v]$，那么就有 $edge[i].dis \geq dis[v] - dis[u]$， $edge[i].dis \leq dis[u] - dis[v]$。直接建边即可，考虑如果不在 1 到 $n$ 之间的路径的边就直接不管。