学习笔记 - Kruskal重构树 | Lucky

听起来非常高级，其实思路却非常简单

Part1. 什么是 Kruskal 重构树

（以下简称重构树）

Kruskal 生成树算法大家都知道，但是重构树就不一定了。普通的生成树算法只是把原图中的边贪心地加到生成树里面，而重构树是将加入生成树的边转成点、边权转成点权 而建出来的一种与原图形态不同的树。

（下面举例都是最小生成树，最大生成树是相反的）

重构树的思想大概是这样：

起初每个点都是一个连通块，且 代表这个连通块的点 都为这个点本身；
先像 Kruskal 生成树一样把边从小到大排序；
然后贪心地枚举每一条边 (u,v)，如果这条边连接是不同连通块的点，就 新建一个点 t，把 t 的 点权设置为边权，并分别连接该点与 u、v 所在连通块的代表节点，然后把 t 设置为两个连通块合并后的代表节点。

这样，我们就得到了一棵重构树（森林，当原图不连通的时候）。不难发现，重构树中：叶子节点代表的是原图中的点，非叶子节点都是边。

与生成树算法不一样 —— 重构树是一棵 有根树！

Part2. 重构树的性质

比较显然的：

是一棵二叉树；

比较有用的：

满足 堆性质（把叶子节点的点权视作0）—— 根的点权大于左右儿子。
原图上的点 u,v 在重构树上的路径是原图中“最大边最小”的路径。
原图上的点 u,v 在重构树上的 LCA 是原图中“最大边最小”的路径的 最大边。

第一点是 Kruskal 生成树算法贪心的结果。第二点是最小生成树的性质，然后第三点结合一二两点即可得出。

这些性质使得重构树非常强大。能够配合倍增做一些限制了图论中诸如“限制 u,v 路径上的最大边不能超过xxx”的题目。

Part3. 例题 NOI2018 - 归程

（想不到 NOI2018 就考了这个，好像是一道送分题，正好可以用来了解重构树）

Part3/1. 题面

>> 传送门-UOJ393

Part3/2. 解析

首先可以想到先处理出每个点到 1 号点的最短距离。然后对于每一个询问，我们求的是：从给定的起点出发，不经过有积水的边能够到达的所有点中，到 1 号点距离最短的点。

我们把条件抽象一下 —— 若不走有积水的边，能从 u 到达 v，就说明 u 到 v 的“最小海拔最大”的路径上的最小海拔超过了水位线。于是就可以想到重构树。

按最大生成树来建立重构树，那么重构树就满足小根堆；重构树上上 u 到 v 的路径就是 u 到 v 的“最小海拔最大”的路径；u,v 的 LCA 就是该路径上的最小海拔。

于是我们从起点出发，不经过积水的边，能够到达的点在重构树上就是“从起点出发，不到达海拔小于等于水位线的点，能够到达的叶子节点（叶子节点表示原图中的点嘛）”。又因为小根堆的性质，不难发现能够到达的点是重构树上的一棵子树！

因此我们要找到这棵子树中：叶子节点所代表的原图上的点与 1 的最短距离。因为是在子树中，所以 DFS 一遍就好了。

至于怎么找这棵子树？倍增找起点的最浅的海拔高于水位线的祖先即可，倍增的时候注意利用好堆性质。

Part3/3. 源代码

/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=2e5,M=4e5;
typedef long long ll;
const ll INF=(1ll<<60);

int cas;
int n,m,fn,q,tmp;
int ch[N*2+3][2],val[N*2+3],pre[N*2+3][20];
ll dis[N+3],mn[N*2+3];
bool fix[N+3];

struct DSU{
    int fa[N+3],head[N+3];
    void Init(){
        for(int i=1;i<=n;i++){
            fa[i]=head[i]=i;
            mn[i]=INF;
        }
    }
    int FindFa(int u){
        if(u==fa[u]) return u;
        return fa[u]=FindFa(fa[u]);
    }
    bool Merge(int u,int v,int wgt){
        int fu=FindFa(u),fv=FindFa(v);
        if(fu==fv) return false;
        fn++;
        ch[fn][0]=head[fu];
        ch[fn][1]=head[fv];
        val[fn]=wgt;
        head[fv]=fn;
        fa[fu]=fv;
        return true;
    }
}D_;
struct GNODE{
    int to,len;GNODE *nxt;
    GNODE(){}
    GNODE(int _t,int _l,GNODE *_n):to(_t),len(_l),nxt(_n){}
};
struct GRAPH{
    GNODE pol[M*2+3],*ncnt,*head[N+3];
    void Init(){
        for(int i=1;i<=n;i++) head[i]=NULL;
        ncnt=pol;
    }
    void AddEdge(int u,int v,int len){
        GNODE *p=++ncnt,*q=++ncnt;
        *p=GNODE(v,len,head[u]);head[u]=p;
        *q=GNODE(u,len,head[v]);head[v]=q;
    }
    GNODE* operator [](int id){return head[id];}
}G_;
struct EDGE{
    int u,v,wgt;
    EDGE(){}
    EDGE(int _u,int _v,int _w):u(_u),v(_v),wgt(_w){}
}E_[M+3];

bool cmpEDGE(const EDGE &A,const EDGE &B){return A.wgt>B.wgt;}
void Kruskal(){
    sort(E_+1,E_+1+m,cmpEDGE);
    for(int i=1;i<=m;i++)
        D_.Merge(E_[i].u,E_[i].v,E_[i].wgt);
}
void Dijkstra(){
    priority_queue< pair<ll,int> > que;
    que.push(make_pair(dis[1]=0,1));
    while(!que.empty()){
        int u=que.top().second;que.pop();
        if(fix[u]) continue;
        fix[u]=true;
        for(GNODE *it=G_[u];it;it=it->nxt){
            int v=it->to;
            if(!fix[v] && dis[v]>dis[u]+it->len)
                que.push(make_pair(-(dis[v]=dis[u]+it->len),v));
        }
    }
}
ll DFS(int u,int fa){
    pre[u][0]=fa;
    for(int i=1;i<=19;i++)
        pre[u][i]=pre[pre[u][i-1]][i-1];
    if(u<=n) return mn[u]=dis[u];
    return mn[u]=min(DFS(ch[u][0],u),DFS(ch[u][1],u));
}
void Init(){
    memset(pre,0,sizeof pre);
    memset(mn,0x3f,sizeof mn);
    memset(fix,false,sizeof fix);
    memset(dis,0x3f,sizeof dis);
    memset(ch,0,sizeof ch);
    G_.Init();
    D_.Init();
    fn=n;
}
int Fetch(int u,int lim){
    for(int i=19;i>=0;i--)
        if(pre[u][i] && val[pre[u][i]]>lim)
            u=pre[u][i];
    return u;
}
int main(){
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&n,&m);
        Init();
        for(int i=1;i<=m;i++){
            int len;
            scanf("%d%d%d%d",&E_[i].u,&E_[i].v,&len,&E_[i].wgt);
            G_.AddEdge(E_[i].u,E_[i].v,len);
        }
        Dijkstra();
        Kruskal();
        for(int i=fn;i;i--)
            if(!pre[i][0])
                DFS(i,0);
        int vS;
        scanf("%d%d%d",&q,&tmp,&vS);
        long long las=-1;
        while(q--){
            int frm,hgt;
            scanf("%d%d",&frm,&hgt);
            if(las!=-1){
                frm=(frm+tmp*las-1)%n+1;
                hgt=(hgt+tmp*las)%(vS+1);
            }
            printf("%lld\n",las=mn[Fetch(frm,hgt)]);
        }
    }
    return 0;
}

The End

Thanks for reading!

时间越过越快了……