【APIO2020】交换城市（Kruskal重构树）

Description

给定一个 \(n\) 个点，\(m\) 条边的无向连通图，边带权。

\(q\) 次询问，每次询问两个点 \(x, y\)，求两点间的次小瓶颈路。不存在输出 -1。

Hint

\(1\le n\le 10^5\)
\(n-1\le m\le 2\times 10^5\)
\(1\le q\le 2\times 10^5\)

Solution

若是求最小瓶颈路的话我们会有一个这样的思路：

由于 最小瓶颈路必定在这个图的最小生成树（MST）上，因此我们可以建出 Kruskal 重构树。

何为 Kruskal 重构树？我们回忆一下 Kruskal 求最小生成树的算法，是选取一个跨越两个连通块的边 \((u, v)\) 进行连接。但现在我们不连边，而书 新建一个结点 \(x\)，从 \(x\) 向 \(u, v\) 各连一条边。每一个新建的结点都带有一个点权，权值大小即为对应边的边权。最终得到的 \(2n-1\) 个结点的树形结构，即为 Kruskal 重构树。

如果我们深入挖掘这棵树的性质，不难发现这些新建点必然对应着 MST 中的边。于是 \(x\) 到 \(y\) 的瓶颈路一定是重构树上的一条路径。而我们又可以看出，祖先结点的加入时间是晚于子孙的，因此 祖先的点权必然大于其子孙。最后，不难得到结论——\(x, y\) 两点的瓶颈路即为两点在重构树上的 \(LCA\) 的点权。

以上就是最小瓶颈路的求法。

对于次小瓶颈路我们可以稍加拓展。

既为『次小』，那么必然是有两条。

注意一下这里，我们需要对上述的建树方法做一点改动，原本发现是同一个连通块是我们会直接舍弃这条边。然而我们求次小的，这条边并不一定毫无贡献。直接往所在的连通块连接即可。

由于说明需要，这个重构树还有一个比较显然的性质——一个重构树上的子树，若树根 \(x\) 点权为 \(w\)，那么这棵子树对应一个连通块，块内所有点可以通过权值不超过 \(w\) 的边可以互相到达。

于是对于两个询问点 \(x, y\)，我们只要找到重构树上这样一个点 \(z\)，满足 \(z\) 是两点的祖先，并且其对应连通块存在次小瓶颈路。在建重构树的过程中，我们通过一个标记 \(type\) 来表示子树所对应的连通块是否存在。

对于一个链状的连通块，很显然只有一条路径。

根据这一点，我们可以设计出如下判断条件：

若新建点 \(x\) 只连向了一个点，说明该连通块中 存在环 了，那么 \(type = 1\)。
若连向了两个连通块：
- 如果 两个连通块存在一个非链状块，那么合并后显然也是，\(type = 1\)。
- 如果加上这条边后，发现一个 度数超过 \(2\) 的顶点，那么同样为非链块，\(type = 1\)。
- 否则 \(type = 0\)。

处理询问的时候，我们先其求出 \(LCA\)，然后倍增地往上跳祖先，直到找到一个 深度最大 \(type = 1\) 的点。其点权即为答案。

这个算法的时间复杂度为 \(O((n+m+q)\log (n+m))\)。

/*

 * Author : _Wallace_

 * Source : https://www.cnblogs.com/-Wallace-/

 * Problem : APIO2020 交换城市

 */

#include "swap.h"

#include <algorithm>

#include <vector>

using namespace std;

const int M = 2e5 + 5;

const int N = 1e5 + 5;

int n, m;

struct Edge {

	int u, v, w;

} e[M];

const int V = N + M;

const int LogV = 20;

vector<int> tr[V];

int fa[V][LogV];

int dep[V];

int val[V], ind[V];

bool type[V];

int tot = 0;

int uset[V];

int find(int x) {

	return x == uset[x] ? x : uset[x] = find(uset[x]);

}

void caldep(int x) {

	dep[x] = dep[fa[x][0]] + 1;

	for (auto y : tr[x]) caldep(y);

}

void Kruskal() {

	for (int i = 1; i <= n; i++) uset[i] = i;

	sort(e + 1, e + m + 1, [&](Edge a, Edge b) {

		return a.w < b.w;

	});

	tot = n;

	for (int i = 1; i <= m; i++) {

		int u = e[i].u, fu = find(u);

		int v = e[i].v, fv = find(v);

		int w = e[i].w;

		++tot;

		if (fu == fv) {

			val[tot] = w;

			fa[fu][0] = tot;

			uset[fu] = uset[tot] = tot;

			type[tot] = true;

			tr[tot].push_back(fu);

		} else {

			val[tot] = w;

			fa[fu][0] = fa[fv][0] = tot;

			uset[fu] = uset[fv] = uset[tot] = tot;

			if (++ind[u] > 2 || ++ind[v] > 2) type[tot] = true;

			if (type[fu] || type[fv]) type[tot] = true;

			tr[tot].push_back(fu);

			tr[tot].push_back(fv);

		}

	}

	type[0] = 1;

	for (int j = 1; j < LogV; j++)

		for (int i = 1; i <= tot; i++)

			fa[i][j] = fa[fa[i][j - 1]][j - 1];

	dep[0] = 0;

	caldep(tot);

}

int lca(int x, int y) {

	if (dep[x] < dep[y]) swap(x, y);

	for (int i = LogV - 1; ~i; --i)

		if (dep[x] - (1 << i) >= dep[y])

			x = fa[x][i];

	if (x == y) return x;

	for (int i = LogV - 1; ~i; --i)

		if (fa[x][i] != fa[y][i])

			x = fa[x][i], y = fa[y][i];

	return fa[x][0];

}

void init(int tmp_n, int tmp_m, vector<int> U, vector<int> V, vector<int> W) {

	n = tmp_n, m = tmp_m;

	for (int i = 0; i < m; i++)

		e[i + 1] = Edge{U[i] + 1, V[i] + 1, W[i]};

	Kruskal();

}

int getMinimumFuelCapacity(int x, int y) {

	int z = lca(++x, ++y);

	if (type[z]) return val[z];

	for (int j = LogV - 1; ~j; --j)

		if (!type[fa[z][j]])

			z = fa[z][j];

	z = fa[z][0];

	return z ? val[z] : -1;

}

巴特西

【APIO2020】交换城市（Kruskal重构树）

Description

Hint

Solution

最新文章

热门文章