今天我会kruskal重构树了吗？

我并不会，甚至还欠了一屁股博客要读。

咋办？

https://www.cnblogs.com/ww3113306/p/9746449.html

在普通的kruskal中，如果一条边连接了在2个不同集合中的点的话，我们将合并这2个点所在集合。
而在kruskal重构树中，如果一条边连接了在2个不同集合中的点，我们将新建一个节点出来，并用这个新节点作为一个中转连接这2个集合。
如图就是一棵kruskal重构树，方点表示新建出的节点，圆点是原图中的点，方点点权即边权。

https://blog.csdn.net/hwzzyr/article/details/81190442

相信大家都会Kruskal由于重构树中把原树的点权转换成为了新建节点的边权，这一过程是这样实现的。
首先对边排序
然后使用并查集辅助加边，每新建一条边时：
新建节点index（编号从n+1开始）
将原有两节点所在集合改为index
将原有节点与index连边
新建节点的权值为当前边的边权
给一下简单的代码

void Ex_Kruskal() {
    int ind=n,lim=n<<1; sort(e+1,e+1+m);
    for(int i=1;i<=lim;++i) f[i]=i;
    for(int i=1;i<=m;++i) {
        int fx=getfa(e[i].a),fy=getfa(e[i].b);
        if(fx!=fy) {
            f[fx]=f[fy]=++ind;
            val[ind]=e[i].w;
            add(ind,fx); add(ind,fy);
            if(ind==lim-1) break;
        }
    } return ;
}

https://blog.csdn.net/niiick/article/details/81952126

https://blog.csdn.net/hwzzyr/article/details/81190442

一道题

# Todo

今天我会kruskal重构树了吗？

Like this article? Support the author with

Catalogue

Links

Categories

Archives

Tags

Your browser is out-of-date!