浅谈kruskal重构树

FWT__FFT · 2022-07-06 11:24:04 · 个人记录

Ps：前置知识：基本图论、最小生成树。

kruskal求最小生成树

相信大家对这玩意已经很熟悉了，不过在这里我还是略微提一下。

前置知识：并查集、贪心

kruskal是一种求最小生成树的算法，具体操作：

将所有边按边权从小到大排序。
选取边权最小的一条边。
如果所选的边的两个顶点不属于同一个最小生成树的点集里，将这条边加入边集里，两个点并入点集里；否则继续执行二操作，直至所有点都进入同一个集合里。
将最小生成树上的边权加起来，就可以求得最小生成树的权值。

图例

这里给出核心代码：

int kruskal(){
    sort(e,e+1+m,cmp);
    int ans=0,cnt=0;
    for(int i=1;i<=m;i++){
        int fu=find(e[i].u),fv=find(e[i].v);
        if(fu==fv)continue;
        fa[fu]=fv;
        ans+=e[i].w;
        cnt++;
    }
    if(cnt<n-1)return -1;
    else return ans;
}

证明

刚才提到，kruskal的算法大致就是按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n-1 条边，即形成了一棵树。

现在我们要证明的是：在任何时候，kruskal算法选的边都被最小生成树的边集所包含。

很容易想到可以用数学归纳法证明,具体证明如下;

对于算法刚开始时，最小生成树存在，命题成立。

我们可以假设当前边集为 E，令 T 为这张图的最小生成树，我们考虑下一条要加进来的边 e。显然当 e \in T 时命题成立，否则 T+e 一定存在一个环。

考虑这个环上不属于 E 的另一条边 f,可以知道有且仅有一条满足条件的边 f。

首先可以确定的是 f \ge e,否则 f 肯定会在 e 之前被选取。

其次 f \le e,要不然 T-e+f 就是一棵比 T 还优的生成树。

综上，显然 f = e。

所以，E \in T-e+f,并且也是一棵最小生成树，命题成立。

正文

好的，前置知识已经全部讲完了，接下来切入正题：

kruskal重构树

给定 n 个点 m 条边的无向图，第 i 条边有一个边权 w_i,现在有 T 个询问，对于每次查询会给出两点 u,v，求 u,v 两点之间所有路径中的最长边的最小值是多少。（1 \le n \le 15000,1 \le m \le 30000,d_i \le 10^9,T \le 15000）

首先我们考虑暴力，以 u 为起点进行深度优先搜素枚举每一条路径求最大值，复杂度 O\left ( nmk \right ) ，显然会TLE。

我们再考虑用最小生成树优化，很显然最长边最小的那条路径的边集属于整张图最小生成树的边集（听起来有些拗口，大家请见谅），于是我们很容易想到求出最小生成树，然后暴力求两点之间最小生成树上的最长边，复杂度 O\left ( nk+mlogm+m \right )，这对于暴力来讲已经是一个不错的优化了，但是还是会TLE。

正解

先看一张图：（图片来源于CSDN博客-------Gragh Theory--------，在此深表感谢）

上面这张图清楚地表示出了kruskal重构树的建树过程，具体它是这样构造的：（可以结合图来看）：

将边权从小到大排个序（不用我说）
选取当前边权最小的一条边，令两个顶点为 u,v，如果 u,v 不在同一个并查集里，那么将其合并，并且新建一个节点 p,将其点权设为 u→v 这条边的边权，重复执行此操作直至所有点都加入同一个并查集。

很显然，kruskal重构树满足这样三个性质：

它是个二叉树
满足大根堆的性质（即满足任一节点满足其点权大于左儿子和右儿子）

所以现在我们只需要先建树，然后再求 LCA(u,v) 就行了，复杂度 O(m+nlogn)，可以过。

贴上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1000;
const int M=N*2;
const int INF=1e9+7;
int cnt;
int n,m,k;
struct edge{//构建边结构体
    int u,v,w;
    bool operator <(const edge &a)const{//重载运算符
        return w<a.w;
    }
}e[M];
int val[M];
int f[N][25];
int ch[N][2];
int sum;
void add_edge(int u,int v,int w){//加边函数
    e[++sum]={u,v,w};
}
int fa[N];
int find(int x){//并查集find函数
    if(x==fa[x])return x;
    else return fa[x]=find(fa[x]);
}
int dep[N];
void dfs(int x){//递归搜索
    if(!ch[x][0]&&!ch[x][1])return;
    dep[ch[x][0]]=dep[ch[x][1]]=dep[x]+1;
    dfs(ch[x][0]);
    dfs(ch[x][1]);
}
int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(dep[f[x][i]]>=dep[y])x=f[x][i];
        if(x==y)return x;
    }
    for(int i=20;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main(){
    cin>>n>>m>>k;
    cnt=n;
    int u,v,w;
    sum=0;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    for(int i=1;i<=n*2;i++){
        fa[i]=i;
    }
    sort(e+1,e+1+m);
    for(int i=1;i<=m;i++){
        int fu=find(e[i].u);
        int fv=find(e[i].v);
        if(fu!=fv){
            cnt++;
            ch[cnt][0]=fu;
            ch[cnt][1]=fv;
            fa[fa[e[i].u]]=fa[fa[e[i].v]]=f[fa[e[i].u]][0]=f[fa[e[i].v]][0]=cnt;
            val[cnt]=e[i].w;
        }
    }
    dep[cnt]=1;
    dfs(cnt);
    for(int i=1;i<=20;i++){
        for(int j=1;j<=2*n;j++){
            f[j][i]=f[f[j][i-1]][i-1];
        }
    }
    int x,y;
    while(k--){
        cin>>x>>y;
        cout<<val[LCA(x,y)]<<endl;
    }
    return 0;
}
/*
input:
5 6 2
1 4 2
1 5 1
4 5 2
2 4 1
2 3 4
3 5 3
2 3
1 2
output:
3
2
*/

kruskal重构树到这里就讲完了，放两道例题：

P1967货车运输

P7834 Peaks 加强版

总结

其实图论有些知识还是很精妙的，希望OIer们能多学习学习图论相关的知识，最后祝大家的OI生涯一帆风顺！

小广告

OI-Wiki是个好东西