最小瓶颈路（Network） 加强版（Kruskal重构树+欧拉序求lca）

标签：temp   class   赋值   clu   算法   long   while   编号   amp   

题目描述

给定一个 \(n\) 个点 \(m\) 条边的无向连通图，编号为 \(1\) 到 \(n\) ，没有自环，可能有重边，每一条边有一个正权值 \(w\) 。
给出 \(q\) 个询问，每次给出两个不同的点 \(u\) 和 \(v\) ，求一条从 \(u\) 到 \(v\) 的路径上边权的最大值最小是多少。

对于所有数据，\(n \le 70000\)，\(m \le 100000\)，\(q \le 10000000\)，\(1 \le w_i \le 10^9\)。

Analysis

这显然是可以用最小生成树+树上倍增实现的，但是我们看到数据范围就感到事情不妙，这个询问必须\(O(1)\)求。这就要用到我们的Kruskal重构树了。

什么是Kruskal重构树

Kruskal重构树是在进行Kruskal算法求最小生成树时将边权变为点权并将其连起来所构成的树形结构。

如何构建

在执行Kruskal算法时如果一条边被选入了最小生成树的集合，我们新建一个点，并将其点权赋值为该边边权。将新建的点连向该边两端点所在的连通块的根节点，并将其合并，该新点作为新的根节点。

原来存在的点的点权即为\(0\)。

代码实现：

for (register int i = 1; i = limit) break;//建好了直接break
	}
}

Kruskal重构树的性质

1，共有\(2n-1\)个节点。

原来的n个点，最小生成树上每条边一个节点，共n-1个记节点。

2，这是一个二叉树

显然。

3，这是一个大根堆

因为后来加的节点的权值一定并前面的大，所以这也显然。

4，原树两点之间的边权最大值是重构树上两点Lca的权值

首先有个引理：这条边一定在最小生成树路径上。

而我们发现Kruskal重构树其实只是将边换成了点，所以这个最长边其实就是在重构树上路径上的最大点权。又因为这是大根堆所以一定是lca。

有了这些性质我们发现如果一个问题给了你一张图，要你询问两点间瓶颈路的问题多半都可以用kruskal重构树做。

现在来解决上面的题，其实就是个模板题，求两点lca就行。可是倍增和树剖都要\(O(\log{n})\)的复杂度怎么办？其实还有一种\(O(1)\)求lca的方法。

我们先求出一棵树的欧拉序，深度和每个节点在欧拉序中最早出现的位置。

欧拉序就是你在遍历到每个节点在第一遍遍历和递归遍历完每个儿子后都加进去所形成的序列。这样一共会有\(2n-1\)个，有趣的是证明和重构树的性质1完全一样。

这样我们发现对于两个节点其lca必然在其第一次出现的位置中间，且lca是深度最小的点，那我们可以用rmq来做，st单次查询的时间复杂度为\(O(1)\)。

完整代码：

/*
喂糖：C6H12O6 
*/
#include 
using namespace std;
typedef long long ll;
const int N = 140010;
const int M = 100010;
const int mod = 1e9 + 7;
template  void inline read(T &x) {
	T f = 1;
	char ch = getchar();
	for (; ‘0‘ > ch || ch > ‘9‘; ch = getchar()) if (ch == ‘-‘) f = -1;
	for (x = 0; ‘0‘ > 1] + 1;
	}
	for (register int i = 1; i  first[v]) swap(u, v);
	u = first[u]; v = first[v];
	int d = v - u + 1;
	int k = lg2[d];
	if (dep[st[u][k]] = limit) break;
		}
	}
	dfs(cnt);
	st_init();
	read(q);
	read(A); read(B); read(C); read(P);
	while (q--) {
		int u = rnd() % n + 1;
		int v = rnd() % n + 1;
		ans = ans + val[lca(u, v)];
		while (ans >= mod) ans -= mod;
	}
	printf("%d", ans);
	return 0;
}

最小瓶颈路（Network） 加强版（Kruskal重构树+欧拉序求lca）

标签：temp   class   赋值   clu   算法   long   while   编号   amp   

原文地址：https://www.cnblogs.com/zcr-blog/p/13381192.html