Kruskal重构树

· · 个人记录

清北食学堂day4，第一次听说了Kruskal重构树，还是要学习一个

能用来做什么？

Kruskal重构树可以在线地求解带权无向图上，两点间所有路径中，权值最大（小）的边权值最小（大）的问题一看就很最小生成树

怎么做？

以最小生成树为例

普通的Kruskal求最小生成树，是在加边的过程中，利用冰碴鸡并查集检查是否会生成环，直接合并并查集并对边的端点u,v直接连边

而生成kruskal重构树，在加边过程中，则会进行如下操作：

建立一个新的点x，点权为边的权值，将u,v（或其所处树之树根）作为x的儿子 图源：https://blog.csdn.net/wu_tongtong/article/details/77601523

有什么性质？

这样生成的树有着十分优美的性质：

1：二叉树

2：最小生成树与重构树两点间路径上边权（点权）最大值相等

3：子节点点权小于父节点（大根堆）

4：最小生成树上两点间路径最大边权等于重构树上两节点的LCA之点权

真棒，有题吗？

bzoj3712 Network

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 < = 20,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

这就是裸题吧= = 直接用kruskal重构树秒之

Code

自己稍微YY了一下丑得一锤

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#define maxn 15010
#define maxm 30010
using namespace std;

int n,m,k;
int prt[maxn*2][25],ch[maxn*2][2],uprt[maxn*2],dep[maxn*2];
long long pts[maxn*2];

struct edge
{
    int u,v;
    long long w;
}ing[maxm];

bool cmp(const edge &a,const edge &b)
{
    return a.w<b.w;
}

int getroot(int x)
{
    return uprt[x]==x?x:uprt[x]=getroot(uprt[x]);
}

void kruskal()
{
    register int i;
    int k=0;
    for(i=1;i<=n*2;++i)
        uprt[i]=i;
    for(i=1;i<=m;++i)
    {
        int r1=getroot(ing[i].u),r2=getroot(ing[i].v);
        if(r1!=r2)
        {
            ++k;
            uprt[r1]=uprt[r2]=prt[r1][0]=prt[r2][0]=n+k;
            ch[n+k][0]=r1;
            ch[n+k][1]=r2;
            pts[n+k]=ing[i].w;
            if(k==n-1)
                return;
        }
    }
}

void dfs(int u,int depth)
{
    dep[u]=depth;
    register int i;
    int v;
    for(i=1;(1<<i)<=dep[u];++i)
    {
        prt[u][i]=prt[prt[u][i-1]][i-1];
    }
    if(ch[u][0])
        dfs(ch[u][0],depth+1);
    if(ch[u][1])
        dfs(ch[u][1],depth+1);
}

int LCA(int x,int y)
{
    if(dep[x]<dep[y])
        swap(x,y);
    register int i;
    for(i=20;i>=0;--i)
        if(dep[x]-(1<<i)>=dep[y])
            x=prt[x][i];
    for(i=20;i>=0;--i)
        if(prt[x][i]!=prt[y][i])
        {
            x=prt[x][i];
            y=prt[y][i];
        }
    x=prt[x][0];
    return x;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    register int i;
    int x,y;
    for(i=1;i<=m;++i)
        scanf("%d%d%lld",&ing[i].u,&ing[i].v,&ing[i].w);
    sort(ing+1,ing+m+1,cmp);
    kruskal();
    dfs(2*n-1,1);
    for(i=1;i<=k;++i)
    {
        scanf("%d%d",&x,&y);
        printf("%lld\n",pts[LCA(x,y)]);
    }
    return 0;
}

另外，NOI2018 D1T1 归程，也要用到Kruskal重构树

BZOJ 3551 Peaks加强版 Kruskal重构树+主席树

待AC。。。

题外话...

学习kruskal重构树过程中，这篇博客给了我很大的便利和启发，本文的一些内容也参考了这篇博客： https://blog.csdn.net/oi_konnyaku/article/details/78757761

非常感谢博客作者的心血，为后来者铺平了道路