D22 Kruscal重构树 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/U201076 ↗

题目描述

给定一张 $N$ 个点的无向图，记为 $1\cdots N$ 。

图中有 $M$ 条边，第 $j$ 条边的长度为 $d_j$ 。

现在有 $K$ 个询问，每个询问的格式为 $A\ \ B$ ，表示询问从 $A$ 走到 $B$ 的所有路径中，最长边的最小值为多少。

输入格式

第一行为三个整数 $N, M, K$ 。

第二行到第 $M+1$ 行，每行三个整数 $X, Y, D$ ，表示从 $X$ 与 $Y$ 之间有一条长度为 $D$ 的边。

第 $M+2$ 行到第 $M+K+1$ 行，每行两个整数 $A, B$ ，意义如上。

输出格式

共 $K$ 行。

对于每个询问，输出最长边的最小值。

输入 #1

plaintext

输出 #1

plaintext

$1 \leq N \leq 15000$

$1 \leq M \leq 30000$

$1 \leq D_j \leq 10^9$

$1 \leq K \leq 15000$

算法解析：#

Kruskal 重构树：按边权从小到大做 Kruskal，每次合并两个连通块时新建一个权值为该边权的虚点作为两者的父节点。这样得到一棵二叉重构树，其中任意两点的 LCA 权值就是这两点间所有路径中最大边权的最小值（最小瓶颈路）。查询用 LCA 即可。

具体算法流程：

对于此题来说，将边权从小到大排序用并查集维护两点的联通性，若祖先不相同，那么新建一个节点，权值为边权。左右儿子分别为两个点这样建出来的树，我们称之为Kruskal重构树

它有许多美妙的性质

是一颗二叉树两点的LCA的点权为原图中最大值最小的路径上的最大值任意点的权值大于左右儿子的权值，是一个大根堆对于此题的样例来说，建出来的图大概长这样

py代码实现#

略

C++代码实现#

/*EHnotgod————
..............#######.....#.....#..............
..............#...........#.....#..............
..............#######.....#######..............
..............#...........#.....#..............
..............#######.....#.....#..............
*/
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define range(i, a, b) for (int i = (a); i < (b); ++i)
#define def(name, ...) auto name = [&](__VA_ARGS__)

const int N=200006;
int n, m, q;
struct edge{
  int u,v,w;
  bool operator<(const edge &t)const
  {return w < t.w;}
}edge[N];
int fa2[N],ans,cnt;
vector<int> value(N, 0);
vector<vector<int>> e(N, vector<int>());
int find(int x){
  if(fa2[x]==x) return x;
  return fa2[x]=find(fa2[x]);
}
void kruskal(){
  sort(edge,edge+m);
  cnt = n;
  for(int i=1;i<N;i++)fa2[i]=i;
  for(int i=0; i<m; i++){
    int x = find(edge[i].u);
    int y = find(edge[i].v);
    if(x!=y){
        cnt++;
        fa2[x]=cnt;
        fa2[y]=cnt;
        value[cnt] = edge[i].w;

        e[x].push_back(cnt);
        e[y].push_back(cnt);
        e[cnt].push_back(x);
        e[cnt].push_back(y);
    }
  }
}
int f[N][22],dep[N];

void dfs(int u,int fa){
  f[u][0]=fa; dep[u]=dep[fa]+1;
  for(int i=1;i<=20;i++) //u的2,4,8...祖先
    f[u][i]=f[f[u][i-1]][i-1];
  for(int v:e[u])
    if(v!=fa) dfs(v,u);
}
int lca(int u,int v){
  if(dep[u]<dep[v]) swap(u,v);
  for(int i=20;~i;i--) //u先大步后小步向上跳，直到与v同层
    if(dep[f[u][i]]>=dep[v]) u=f[u][i];
  if(u==v) return v;
  for(int i=20;~i;i--) //u,v一起向上跳，直到lca的下面
    if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
  return f[u][0];
}
// vector<int> a(n, 0);
// vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
void solve() {
	cin >> n >> m >> q;
	for (int i = 0; i < m; i++){
		cin >> edge[i].u >> edge[i].v >> edge[i].w;
	}
    kruskal();

    dfs(cnt, 0);
    
    while (q--){
        int u, v; cin >> u >> v;
        int uv = lca(u, v);
        cout << value[uv] << endl;
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int t;
	t = 1;
	while (t--) {
		solve();
	}
	return 0;
}