Kruskal重构树

前两天打了noi2018网上同步赛,看标算重构树以为是什么高明的dark数据结构,一看还是挺小清新的。

先考虑在做Kruskal的过程中,每次会选取一条当前最优的边并加入生成树。在这个过程中,我们可以加入一个虚节点表示当前的这条边,点权值即为边权。由于一条边只能有两个端点,所以这棵树必然是一棵二叉树,就可以妙妙地维护了啊!

然后这个树有一些很棒的性质,比如说一条边到根的路径上的点权是单调的,两点在图中的最长边的最小值即为两点在重构树上的LCA等等(自己想啦~逃

裸题:bzoj3732

打法自己想想吧233

实在不行可以参考我的代码:

void Krus ()
{
    sort(e + 1, e + m + 1, cmp);
    for (int i = 1; i <= n; ++i) ch[i][0] = ch[i][1] = 0;
    for (int i = 1; i <= m; i++)
    {
        int fu = gf(e[i].u), fv = gf(e[i].v);
        if (fu == fv) continue;
        val[++ver] = e[i].a;
        ch[ver][0] = anc[fu], ch[ver][1] = anc[fv];
        //maintain something here
        fa[fu] = fv, anc[fv] = ver;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注