首页 > 其他分享 >图论笔记

图论笔记

时间：2024-02-12 22:35:10浏览次数：26  
标签：图论 mathbf int 短路 最小 笔记 生成 fa

最短路相关

最短路基础

  • \(\mathbf{Floyed}\) 求最短路

本质上是 dp。设 \(f(w, i, j)\) 表示当前松弛到第 \(w\) 轮，\(i \rightarrow j\) 的最短路是 \(f(w, i, j)\)。转移显然是：

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

\(w\) 显然可以滚掉。时间复杂度 \(O(n ^ 3)\)。

松弛的时候，最外层需要枚举中间节点才能保证一边松弛就求出最短路。如果按照 \(ijk\) 或者 \(ikj\) 的顺序枚举则需要两遍 / 三遍。不过三遍之内一定可以求出最短路。

该算法最重要的作用不是求最短路，而是计算传递闭包。

  • \(\mathbf{Floyed}\) 求传递闭包

传递闭包的作用是对于所有点对 \((i, j)\)，求出从 \(i\) 能否走到 \(j\)。

设 \(f(w, i, j)\) 表示当前松弛到第 \(k\) 轮，从 \(i\) 是否能够走到 \(j\)。转移明显是

\[f(w, i, j) = f(w, i, j) \ \mathbf{Or} \ f(w - 1, i, k) \ \mathbf{and}\ f(w - 1, k, j) \]

时间复杂度 \(O(n ^ 3)\)。

for (int k = 1; k <= n; k ++ )
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= n; j ++ )
			if (i != k and j != k)
				f[i][j] |= f[i][k] & f[k][j];

考虑 \(n = 5000\) 时的做法。设 \(f(w, i)\) 表示松弛到第 \(w\) 轮，从 \(i\) 出发到所有点的状态，用一个二进制数表示。若第 \(j\) 位为 \(1\) 则表示从 \(i\) 可以到达 \(j\)，反之不能到达。转移如下：

\[f(w, i) = f(w - 1, j) \ \mathbf{Or} \ f(w - 1, i) \]

使用 bitset 优化此过程，可以做到 \(O(\dfrac{n ^ 3}{\omega})\)。

for (int j = 1; j <= n; j ++ )
	for (int i = 1; i <= n; i ++ )
		if (f[i][j]) f[i] |= f[j];
  • \(\mathbf{dijkstra}\) 求最短路

单源最短路。设 \(f_i\) 表示从源点出发到达 \(i\) 号点的最短路长度。每次找到距离 \(i\) 号点距离最近的点进行转移。假设 \(j\) 距离 \(i\) 最近，则转移为

\[f_j = \min\{f_j, f_i + w_{i, j}\} \]

暴力的转移时间复杂度 \(O(n ^ 2)\)。将 \(f\) 推进优先队列中，时间复杂度 \(O(m \log m)\)。如果手写堆时间复杂度 \(O(m \log n)\)，但是一般没有人写。如果手写斐波那契堆时间复杂度 \(O(n \log n)\)，但是 no practical。

该算法仅适用于边权非负的图。

  • \(\mathbf{SPFA}\) 求最短路

仍然是上面的思路。设 \(f_{i}\) 表示源点到 \(i\) 号点的最短路径长度。使用一个队列来维护访问过的点集，并且标记有哪些点在队列里。转移方式和 dijkstra 相同，但是在进队和出队的时候需要进行判断。

每个点的入队次数最多为 \(O(m)\)。时间复杂度 \(O(nm)\)。该算法在随机图中表现良好（\(O(n + m)\)），但是在并不难卡掉。

该算法最大的作用应该是判断负环以及费用流的计算。

\(\mathbf{SPFA}\) 判负环：
记录一个数组 cnt，记录每个点出队的次数。如果一次点出队的次数 \(> n\) 说明有负环。

最短路问题的难点通常在于模型的构建，建图方式通常有下面几种：

  • 建反图。通常用于求多源单汇最短路。

  • 虚拟原点。通常用于多源单汇最短路。

  • 同余最短路。

  • 建立分层图。

  • 数据结构优化建图等。

下面是几道例题。

例题 \(1\)：ZROI 某题 D. [2023CSP七连 Day2] 移动金币

给出一个 \(n\) 个点 \(m\) 条边的有向图，点的编号为 \(1\) 到 \(n\)，第 \(i\) 条边从 \(u_i\) 出发连向 \(v_i\)，长度为 \(w_i\)。

你想要在这张图上玩若干轮游戏。在一轮游戏中，你会先选定一个点 \(p\)（\(p\ne1\)）
，接着在 \(1\) 号点和 \(p\) 分别放置一枚金币。你可以沿着有向边任意移动金币，但需要花费边长对应的时间。你的目标是要让两枚金币移动到同一个点，并且最小化总时间。你需要对 \(p \le n\) 都计算出答案。

设 \(1\) 号点到 \(i\) 号点的最短路为 \(f_i\)，\(p\) 号点到 \(i\) 号点的最短路为 \(g_i\)。则 \(\min\{f_i + g_i\}\) 就是答案。时间复杂度 \(O(nm \log n)\)，这是无法接受的。

考虑优化建图方式。从 \(1\) 号点开始做单源最短路，对于每个点求出 \(f_i\)。

接下来将所有边的方向反向，建立反图。

接下来 建立虚拟原点 \(0\) 号点。对于所有节点 \(i\) 建立 \(0 \rightarrow i\) 的有向边，边权为 \(f_i\)。求出从 \(0\) 号点到 \(p\) 号点的最短路即为答案。

这样的建图方式是考虑到：答案是由一段正向路径和一段反向路径拼凑而成的。将其中任意一段反向取反都可以使用单源最短路解决。上述算法时间复杂度 \(O(m \log n)\)。

同余最短路

魏老师曾经说过：同余最短路还在写最短路？时代的眼泪！

于是不要同余最短路了，还是老老实实转圈吧。

例题 \(1\)： P3403 跳楼机

第一次做这道题还是两年前，当时啥都不会。。。

题意大概是：求 \(1 \sim h\) 中，能够被 \(x, y, z\) 通过 \(x \times p_1 + y \times p_2 + z \times p_3\) 表示的数的个数。其中 \(p_1, p_2, p_3 \ge 0\)。

这是同余最短路的经典题。设 \(f_i\) 表示 \(i\) 是否能被表示，则 \(f_i = f_{i - x} \ \mathbf{Or}\ f_{i - y} \ \mathbf{Or}\ f_{i - z}\)。时间复杂度 \(O(h)\)，显然爆炸。

看来这种完全背包的思路是完全不可行的。

假设起始楼层为 \(0\)。设 \(d_i\) 表示能够到达的最低的 \(\bmod\ x = i\) 的楼层。有转移

\[i \xrightarrow{y} (i + y) \bmod \ x \]

\[i \xrightarrow{z} (i + z) \bmod \ x \]

这样可以建出一个点数为 \(x\)，边数为 \(2x\) 的图。\(d_i\) 便是从 \(0\) 号点出发的单源最短路。dijkstra 即可。

最后，对于每个 \(i < x\)，都对答案有贡献 \(\left \lfloor \dfrac{h - d_i}{x} \right \rfloor\)。时间复杂度 \(O(x \log x)\)。

scanf("%lld", &H); H -- ;
scanf("%lld%lld%lld", &x, &y, &z);
for (int i = 0; i < x; i ++ )
	add(i, (i + y) % x, y),
	add(i, (i + z) % x, z);
priority_queue<PII, vector<PII>, greater<PII>> q;
std::fill(d, d + x, INF); d[0] = 0; q.push({0, 0});
while (q.size()) {
	auto u = q.top().second; q.pop();
	for (int i = h[u]; i; i = ne[i]) {
		int v = e[i]; if (d[v] > d[u] + w[i])
			d[v] = d[u] + w[i], q.push({d[v], v});
	}
}
for (int i = 0; i < x; i ++ )
	if (H >= d[i]) ans += (H - d[i]) / x + 1;
cout << ans << endl; return 0;

下面介绍魏老师的转圈技巧。魏老师的 \(\mathbf{blog}\)

设 \(m = v_1\)，即体积最小的物品的体积。考虑模 \(m\) 意义下的完全背包，其形成一个大小为 \(m\) 的环。

对于每一个体积为 \(v_i\) 的物品，其与该环上形成 \(\gcd(v_i, m)\) 个子环。从 \(0\) 点出发兜兜转转最终一定可以回到 \(0\) 点，而且步数最多 \(\gcd(v_i, m)\) 步。只要沿着自环转两圈转移即可。

不理解为什么复杂度是 \(O(nm)\)，感觉应该是 \(O(nm \log n)\)。

以 P3403 跳楼机 一题为例，代码大致如下：

scanf("%lld", &H); H -- ;
scanf("%lld%lld%lld", &v[1], &v[2], &v[3]);
sort(v + 1, v + 4), m = v[1];
fill(f, f + m, INF); f[0] = 0;
for (int i = 2; i <= 3; i ++ )
	for (int j = 0, lim = gcd(v[i], m); j < lim; j ++ )
		for (int t = j, c = 0; c < 2; c += t == j) {
			int p = (t + v[i]) % m;
			f[p] = min(f[p], f[t] + v[i]), t = p;
		}
for (int i = 0; i < m; i ++ )
	if (f[i] <= H) ans += (H - f[i]) / m + 1;
cout << ans << endl; return 0;

从速度上来看，转圈算法比同余最短路快得多。因此还是写转圈吧。

和上一题思路相同，区别是 \(n\) 的范围有所不同。通过转圈的方式可以轻易求解。

signed main() {
	scanf("%lld%lld%lld", &n, &l, &r); l -- ;
	for (int i = 1; i <= n; i ++ ) scanf("%lld", &v[i]);
	sort(v + 1, v + n + 1, greater<int>());
	while (!v[n]) n -- ; sort(v + 1, v + n + 1), m = v[1]; 
	fill(f, f + m, INF); f[0] = 0;
	for (int i = 2; i <= n; i ++ )
		for (int j = 0, lim = gcd(v[i], m); j < lim; j ++ )
			for (int t = j, c = 0; c < 2; c += t == j) {
				int p = (t + v[i]) % m;
				f[p] = min(f[p], f[t] + v[i]), t = p;
			}
	for (int i = 0; i < m; i ++ ) {
		if (f[i] <= r) ans += (r - f[i]) / m + 1;
		if (f[i] <= l) ans -= (l - f[i]) / m + 1;
	}
	cout << ans << endl; return 0;
}

膜拜一下魏老师，魏老师太强了。

差分约束

设 \(x_1, x_2, \cdots x_n\) 是若干变量，\(c_1, c_2 \cdots c_m\) 是若干常量。差分约束用于求解若干形如 \(x_i - x_j \le c_k\) 的不等式组的解集。

将 \(x_i - x_j \le c_k\) 变形得到 \(x_i \le x_j + c_k\)，这与单源最短路中的三角形不等式非常相似。因此考虑通过图论方式解决该问题。

建立虚拟源点 \(0\)，设 \(d_i\) 表示源点到 \(i\) 号点的最短路。初始时 \(d_0 = 0\)。

对于每个不等式组 \(x_i - x_j \ge c_k\)，从 \(j\) 向 \(i\) 连一条边权为 \(c_k\) 的边。为了保证图的连通性，从 \(0\) 号点向所有点连接一条边权为 \(0\) 的边。若该图中存在负环，则证明无解。否则，\(x_i = d_i\) 便是一组解。

一些典型的模型转化方式：

经典例题。按照题意构造图论模型即可。

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i ++ ) {
		int op, a, b, c; scanf("%d%d%d", &op, &a, &b);
		if (op == 1) scanf("%d", &c), add(a, b, -c);
		if (op == 2) scanf("%d", &c), add(b, a, c);
		if (op == 3) add(a, b, 0), add(b, a, 0);
	} for (int i = 1; i <= n; i ++ ) add(0, i, 0);
	queue<int> q; q.push(0); st[0] = 1;
	memset(d, 0x3f, sizeof d); d[0] = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		st[u] = 0; cnt[u] ++ ; 
		if (cnt[u] > n) { flg = 1; break; }
		for (int i = h[u]; i; i = ne[i]) {
			int v = e[i]; if (d[v] > d[u] + w[i]) {
				d[v] = d[u] + w[i]; if (!st[v])
					q.push(v), st[v] = 1;
			}
		}
	} puts(flg ? "No" : "Yes"); return 0;
}

生成树相关

最小生成树基础

  • \(\mathbf{kruskal}\) 求最小生成树

将所有边按照权值从小到大排序。依次枚举每一条边 \((u, v)\)，如果 \(u, v\) 不连通就加上一条 \((u, v)\) 的边。最后即为最小生成树。

将排序方式改为降序即可求出最大生成树。

  • \(\mathbf{Boruvka}\) 求最小生成树

还没仔细研究，研究明白了再写。

非严格次小生成树

首先使用 \(\mathbf{kruskal}\) 求出该图的一个最小生成树。枚举不在最小生成树上的边 \((u, v)\)。拎出 \(u \rightarrow v\) 的路径。设这条路径上的最大值是 \(w'\)，\((u, v)\) 的边权是 \(w\)。设 \(\Delta w = w' - w\)。求出 \(\Delta w\) 的最小值即可。

求出路径的最大值方法比较简单。设 \(f_{i, j}\) 表示从 \(i\) 往上跳 \(2 ^ j\) 步，路径上的最小值。倍增向上跳即可。时间复杂度 \(O(m \log n)\)。

严格次小生成树

依旧沿用上述的算法。如果 \((u, v)\) 路径上的最大值是 \(w_1\)，\((u, v)\) 路径上的次大值为 \(w_2\)。如果 \(w(u, v) = w_1\)，则 \(\Delta w = w - w_2\)。否则 \(\Delta w = w - w_1\)。

瓶颈生成树

无向图 \(G\) 的瓶颈生成树是这样的一个生成树，它的最大的边权值在 \(G\) 的所有生成树中最小。

性质：一棵生成树 \(T\) 为最小生成树是该生成树为瓶颈生成树的充分不必要条件。

最小瓶颈路

无向图 \(G\) 中 \(x \rightarrow y\) 的最小生成路定义为所有 \(x\) 到 \(y\) 的路径中，边权最大值最小的一条。

性质：任意最小生成树上 \(x \rightarrow y\) 的路径均为最小瓶颈路。

注意该性质是最小瓶颈路的充分不必要条件。

最小瓶颈路通常用于代替 kruscal 重构树。经典例题有 P1967 [NOIP2013 提高组] 货车运输

模板题：LOJ #136. 最小瓶颈路

求出该图的最小生成树，最小生成树即为 \(s \rightarrow t\) 路径的最大值。可以直接使用倍增求解，或者使用树剖 ST 表。时间复杂度 \(O((m + n) \log n)\)。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;
struct P { int a, b, c; }p[N];
vector<PII> E[N];
int fa[N][21], mx[N][21], F[N], dep[N], n, m, q;
int find(int x) { return x == F[x] ? x : F[x] = find(F[x]); }
void add(int a, int b, int c) { 
	E[a].push_back({b, c}); E[b].push_back({a, c}); 
}
void dfs(int u, int f) {
	fa[u][0] = f, dep[u] = dep[f] + 1;
	for (auto [v, w] : E[u]) if (v ^ f) mx[v][0] = w, dfs(v, u);
}
int ask(int u, int v, int s = 0) {
	if (find(u) ^ find(v)) return -1;
	if (dep[u] < dep[v]) swap(u, v);
	dep(i, 20, 0) if (dep[fa[u][i]] >= dep[v]) 
		s = max(s, mx[u][i]), u = fa[u][i];
	if (u == v) return s;
	dep(i, 20, 0) if (fa[u][i] != fa[v][i])
		s = max({s, mx[u][i], mx[v][i]}),
		u = fa[u][i], v = fa[v][i];
	s = max({s, mx[u][0], mx[v][0]}); return s;
}
int main() {
	scanf("%d%d%d", &n, &m, &q);
	rep(i, 1, m) scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
	sort(p + 1, p + m + 1, [&](P a, P b) { return a.c < b.c; });
	rep(i, 1, n) F[i] = i;
	rep(i, 1, m) if (find(p[i].a) ^ find(p[i].b))
		add(p[i].a, p[i].b, p[i].c),
		F[find(p[i].a)] = find(p[i].b);
	rep(i, 1, n) if (!dep[i]) dfs(i, 0);
	rep(j, 1, 20) rep(i, 1, n) 
		fa[i][j] = fa[fa[i][j - 1]][j - 1];
	rep(j, 1, 20) rep(i, 1, n) 
		mx[i][j] = max(mx[i][j - 1], mx[fa[i][j - 1]][j - 1]);
	rep(i, 1, q) {
		int s, t; scanf("%d%d", &s, &t);
		printf("%d\n", ask(s, t));
	} return 0;
}

最小差值生成树

P4234 最小差值生成树：求原图的一棵生成树，使得生成树中的最大值减最小值最小。

与 kruscal 求最小生成树的过程相同，将边权从小到大排序。连边过程使用 LCT 代替并查集进行实现。加入新边的过程就是更新最大值的过程。设新边为 \((u, v)\)，删掉树上路径 \(u \rightarrow v\) 的最小值，再连上新边。这一轮操作得到的差值是新边权值减去删边后的全局最小值。

维护全局最小值可以用 multiset 实现。时间复杂度 \(O(m \log n)\)。

最小度限制生成树

给你一个有 \(n\) 个节点，\(m\) 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 \(s\) 的节点正好连了 \(k\) 条边。

考虑 \(f(s)\) 表示与某点相连的边数为 \(x\) 时的最小生成树权值。发现 \(f(s)\) 凸完全单调。

于是考虑 wqs 二分。二分 mid，将与关键点相连的所有边权都减去 mid，表示这个点连上一个边就要减去 mid 的权值。

本质上，wqs 二分是在二分斜率切凸包。将横坐标作为与 \(s\) 相连的边的数量，\(f(x)\) 表示与某点相连的边数为 \(x\) 时的最小生成树权值。二分的 mid 即是斜率，选中一条边就减去一个 mid，这个过程就是直线切凸包的过程。当切点横坐标恰好为 \(k\) 的时候，此时的 mid 即为合法斜率。

求出此时的 \(f(s)\)，加上 \(k \times mid\) 即为答案。注意，可能出现 \(s\) 的度数永远大于 \(k\) 的情况，需要特判。

int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int check(int mid) {
	for (int i = 1; i <= n; i ++ )
		fa[i] = i;
	for (int i = 1; i <= m; i ++ ) {
		if (p[i].u == s or p[i].v == s)
			p[i].w -= mid;
	}
	sort(p + 1, p + m + 1);
	int ecnt = 0, dcnt = 0; sum = 0;
	for (int i = 1; i <= m; i ++ ) {
		int u = p[i].u, v = p[i].v, w = p[i].w;
		if (find(u) == find(v)) continue;
		if (u == s or v == s) dcnt ++ ;
		ecnt ++ ; fa[find(u)] = find(v);
		sum += w;
		if (ecnt == n - 1) break;
	}
	if (ecnt != n - 1) { puts("Impossible"); exit(0); }
	if (dcnt == k) { printf("%lld\n", sum + mid * k); exit(0); }
	for (int i = 1; i <= m; i ++ )
		if (p[i].u == s or p[i].v == s)
			p[i].w += mid;
	return dcnt;
}
signed main() {
	scanf("%lld%lld%lld%lld", &n, &m, &s, &k);
	for (int i = 1; i <= m; i ++ ) {
		auto &[a, b, c] = p[i]; 
		scanf("%lld%lld%lld", &a, &b, &c);
	}
	int l = -30000, r = 30000;
	if (check(l) > k) return puts("Impossible"), 0;
	if (check(r) < k) return puts("Impossible"), 0;
	while (l <= r) {
		int mid = l + r >> 1;
		if (check(mid) <= k) l = mid + 1;
		else r = mid - 1;
	}
	check(l);
	printf("%lld\n", sum + k * l);
	return 0;
}

\(\mathbf{Kruskal}\) 重构树

  • \(\mathbf{Kruskal}\) 重构树定义

    • \(\mathbf{Kruskal}\) 求最小生成树：将边权排序，每次合并两个节点，合并 \(n - 1\) 次得到最小生成树。

    • \(\mathbf{Kruskal}\) 重构树：与 \(\mathbf{Kruskal}\) 求最小生成树的过程相同，区别是每次合并两个节点的时候，新建一个节点，点权为加入的边权。将该新点的左右儿子分别设置成合并的两个节点。合并 \(n - 1\) 轮之后形成的树就是 \(\mathbf{Kruskal}\) 重构树。

  • \(\mathbf{Kruskal}\) 重构树性质

    • 性质 \(1\)：\(\mathbf{Kruskal}\) 重构树形成一个大根堆。

    • 性质 \(2\)：不难发现，\(u \rightarrow v\) 所有简单路径最大值的最小值 = 最小生成树上两点之间路径的最大值 = \(\mathbf{Kruskal}\) 重构树上两点 LCA 的权值。

    • 性质 \(3\)：原图中的所有节点都是 \(\mathbf{Kruskal}\) 重构树的叶子结点。

  • \(\mathbf{Kruskal}\) 重构树应用

    没错还是这道题。建立 \(\mathbf{Kruskal}\) 重构树后，两点 LCA 的权值即为答案。时间复杂度 \(O((m + q) \log n)\)。

    • 求从一个点出发，经过边权不超过 \(V\) 的点能够到达的点集。

    就是 P4197 Peaks 。

    建立原图的最小生成树，从起点沿着点权小于等于 \(V\) 的点往上走直到走不动。设最终走到的点为 \(u\)，则 \(u\) 的子树内点均为所求。

    在这道例题中，由于要询问第 \(k\) 小，直接主席树带走。

    #include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <queue>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )

using namespace std;

const int INF = 2e9;
const int N = 1000010;
const int V = 1e9;
const int M = 1e7;
int idx, cnt, n, m, q, tsp, dep[N], dfn[N], w[N];
int F[N], fa[N][21], sz[N], h[N], rid[N], rt[N];
struct Edge { int a, b, c; }e[N];
vector<int> E[N];
void add(int a, int b) { E[a].push_back(b); }
struct node { int ls, rs, s; }tr[M];
#define lc tr[u].ls
#define rc tr[u].rs
#define mid (l + r >> 1)
void ins(int &u, int v, int l, int r, int x) {
    if (l > x or r < x) return;
    tr[u = ++ idx] = tr[v], tr[u].s ++ ;
    if (l == r) return; ins(lc, tr[v].ls, l, mid, x);
    ins(rc, tr[v].rs, mid + 1, r, x);
}
int ask(int u, int v, int l, int r, int k) {
    if (l == r) return r;
    int s = tr[rc].s - tr[tr[v].rs].s;
    if (s >= k) return ask(rc, tr[v].rs, mid + 1, r, k);
    else return ask(lc, tr[v].ls, l, mid, k - s);
}
int find(int x) { return x == F[x] ? x : F[x] = find(F[x]); }
void dfs(int u, int Fa) {
    fa[u][0] = Fa, dep[u] = dep[Fa] + 1;
    sz[u] = u > n ? 0 : 1; dfn[u] = u > n ? tsp : ++ tsp;
    if (u <= n) rid[tsp] = u;
    for (auto v : E[u]) if (v ^ Fa)
        dfs(v, u), sz[u] += sz[v];
}
int ask(int u, int v, int k) {
    dep(i, 20, 0) if (w[fa[u][i]] <= v) u = fa[u][i];
    if (sz[u] < k) return -1;
    return ask(rt[dfn[u] + sz[u]], rt[dfn[u]], 1, V, k);
}
int main() {
    scanf("%d%d%d", &n, &m, &q); cnt = n;
    rep(i, 1, n) scanf("%d", &h[i]);
    rep(i, 1, m) scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
    sort(e + 1, e + m + 1, [&](Edge a, Edge b) { return a.c < b.c; });
    iota(F + 1, F + n + n + 1, 1); for (auto i : e) 
        if (find(i.a) ^ find(i.b)) {
            w[ ++ cnt] = i.c; add(cnt, find(i.a)), add(cnt, find(i.b));
            F[find(i.a)] = F[find(i.b)] = cnt;
        } w[0] = INF;
    rep(i, 1, cnt) if (find(i) == i) dfs(i, 0);
    rep(j, 1, 20) rep(i, 1, cnt) fa[i][j] = fa[fa[i][j - 1]][j - 1];
    rep(i, 1, tsp) ins(rt[i], rt[i - 1], 1, V, h[rid[i]]);
    rep(i, 1, q) {
        int u, v, k; scanf("%d%d%d", &u, &v, &k);
        printf("%d\n", ask(u, v, k));
    } return 0;
}

标签：图论,mathbf,int,短路,最小,笔记,生成,fa
From： https://www.cnblogs.com/LcyRegister/p/18014196

相关文章

  • esp32笔记[15]-使用LVGL 9.0显示图片
    摘要在esp32s3上使用LVGL9.0显示图片.关键信息编译环境:ESP-IDFv4.4LVGL:9.0board:酷世DIYESP32S3开发板Link:https://item.taobao.com/item.htm?&id=655913924680flashsize:8MBLCDdriver:ILI9341LCDmodule:2.4TFTSPI240x320v1.2Touchdriver:XPT2046......
  • 线段树分治学习笔记
    线段树分治线段树分治是一种可以离线处理带撤销问题的常用手段。一般而言，题目中加入操作很好维护，但删除操作不好维护，这时可以对时间维建线段树，把每一个操作加入其存在时间段对应的线段树节点上，然后处理所有询问，进入一个节点时将这个节点里的操作加入，递归左右儿子，然后撤销这一次做......
  • 快速幂学习笔记
    我们不妨先来看一道例题了解一下快速幂：【模板】快速幂Atemplate.观察到数据，\(a,b\le2^{31}\)，普通的乘法是肯定不行的。因此考虑优化：快速幂。什么是快速幂？顾名思义，就是快速地求出幂（\(a^b\)）。怎么快速地求出幂？将\(a^b\)展开，可得：\[a^b=\underbrace{a\timesa\timesa......
  • 【笔记】矩阵快速幂
    前置芝士快速幂。什么是矩阵？矩阵，是由\(\begin{bmatrix}\end{bmatrix}\)组成的一个方阵（就这么理解好啦）。比如：\(\begin{bmatrix}1&2\\3&4\end{bmatrix}\)是一个\(2\times2\)的矩阵。矩阵乘法矩阵乘法的条件：仅当第\(1\)个矩阵的列数\(=\)第\(2\)个矩阵的行数才有......
  • boruvka 算法学习笔记
    boruvka算法就是最小生成树B算法。B算法的思路是每次对每个连通块，求出它能连出去的权值最小的边，然后再按边权从小到大合并。由于每次操作连通块数至少减半，所以复杂度是\(O(m\logn)\)。1.CF1305GKuroniandAntihype题意：长为\(n\)的数列\(a\)，现在要选择全部数，每一次你......
  • C++——异常处理模块笔记
    异常处理是C++中的重要概念之一，用于处理在程序执行过程中可能发生的错误或异常情况。异常是指在程序执行过程中发生的一些不寻常的事件，例如除零错误、访问无效内存等。C++提供了一套异常处理机制，使得程序可以优雅地处理这些异常，提高程序的可靠性和健壮性。异常是一种程序......
  • 江禾：零散媒体笔记
    零基础绘画练习排线，整齐几何体进阶把想画的东西画像，不断观察修改提高自己审美，分析好看的画为什么好看眼睛和画面要平行明确线条才能进步混剪素材预告片欧美预告片YouTube、Bilibili搜电影搜电影的替代网站纪录片《电影史话》《出神入化：电影剪辑的魔力》《工......
  • 二十八、实践中前端的一些笔记
    display:flex/inline-flex使用了display:flex/inline-flex属性后，子元素横向排列使用了display:flex属性后，父元素不设置宽度，宽度就是100%；不会被子元素宽度撑开；使用了display:inline-flex属性后，父元素不设置宽度，宽度就是所有的子元素宽度之和，会被子元素宽度撑开，实现宽度自......
  • 2-SAT学习笔记
    2-SATk-SAT问题SAT是适定性（Satisfiability）问题的简称。一般形式为k−适定性问题，简称k−SAT。而当k>2时该问题为NP完全的。所以我们只研究k=2的情况。2−SAT，简单的说就是给出n个集合，每个集合有两个元素，已知若干个<a,b>，表示a与b矛盾（其中a与b属于不同的集合）。然后从每个集合选择......
  • 二十一、JS笔记
    JSONimportjson#对象转字符串str=json.dumps(dict,ensure_ascii=False)#ensure_ascii=True或不设置str=json.dumps(dict)#这时前端拿到的是未解码的数据：{"key1":"\u7528\u6237\u8f93...",...}obj=json.loads(str)#字符串转对象jsJSON.parse(str)#字符......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99