kruskal重构树
Description
给你N个点的无向图 (1 <= N <= 15,000),记为:1…N。
图中有M条边 (1 <= M <= 30,000) ,第j条边的长度为: d_j ( 1 < = d_j < = 1,000,000,000).
现在有 K个询问 (1 < = K < = 15,000)。
每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?
Input
第一行: N, M, K。
第2..M+1行: 三个正整数:X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。
第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少?
Output
对每个询问,输出最长的边最小值是多少。
Sample Input
6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
Sample Output
5
5
5
4
4
7
4
5
Hint
1 <= N <= 15,000
1 <= M <= 30,000
1 <= d_j <= 1,000,000,000
1 <= K <= 15,000
Solution
首先如果这道题是可以离线的,那么我们可以将边从小到大排序,每次加边,然后把两个端点所在的联通块并在一起。那么当A,B刚好联通时加的那条边的边权就是答案。但是本题强制在线,所以我们必须先预处理再回答询问。
我们按照kruskal求最小生成树的方式加边,但每次在加边时,新建一个节点,然后把两个联通块(其实是两棵二叉树)的根节点作为其左右儿子,把边权赋值给新建节点。那么我们可以发现这棵树有几个性质。
- 是一棵二叉树(虽然这道题并没有什么卵用);
- 满足父节点的值大于等于儿子节点,是一个大顶堆,这是最关键的一点;
- 原图上任意两点间路径最长边的最小值等于其lca的值;
这种建树的方法称作kruskal重构树。
那么A,B的lca就是所求答案。
Code
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 3e4 + 5;
int n, m, q, cnt, x, y;
int fa[maxn << 1], f[maxn << 1][20], dep[maxn << 1], val[maxn << 1], ch[maxn << 1][2];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
struct edge {
int u, v, w;
bool operator < (const edge &a) const {return w < a.w;}
} e[maxn << 1];
inline int ask(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
int t = dep[u] - dep[v];
for(int i = 0; i < 20; i++) if(t & (1<<i)) u = f[u][i];
for(int i = 19; ~i; i--) {
if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
}
if(u != v) u = f[u][0];
return u;
}
void dfs(int u) {
if(!ch[u][0]) return;
dep[ch[u][0]] = dep[ch[u][1]] = dep[u] + 1;
dfs(ch[u][0]), dfs(ch[u][1]);
}
int main() {
scanf("%d%d%d", &n, &m, &q), cnt = n;
for(int i = 0; i < m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
sort(e, e + m);
for(int i = 1; i < maxn; i++) fa[i] = i, fa[i + maxn] = i + maxn;
for(int i = 0; i < m; i++) {
int u = e[i].u, v = e[i].v;
if(find(u) == find(v)) continue;
ch[++cnt][0] = fa[u], ch[cnt][1] = fa[v];
fa[fa[u]] = fa[fa[v]] = f[fa[u]][0] = f[fa[v]][0] = cnt;
val[cnt] = e[i].w;
}
dfs(cnt);
for(int j = 1; j < 20; j++)
for(int i = 1; i <= cnt; i++) f[i][j] = f[f[i][j-1]][j-1];
for(int i = 0; i < q; i++) {
scanf("%d%d", &x, &y);
printf("%d\n",val[ask(x, y)]);
}
return 0;
}