题解 P4716 【【模板】最小树形图】

· · 题解

写在前面的话

  1. 作者水平不够，如果看不懂，差不多就是我错了
  2. 本文主要是补充tarjan优化朱刘算法这个黑科技，因为大多数人都说只要暴力朱刘就够了，如果不把这个东西介绍出来，它永远也不会成为考点
  3. 本文会顺便简单介绍朱刘，因为网上的证明比较少，它也是tarjan优化的前提，另外感觉其他题解一上来就是一堆生僻的名词，很劝退
  4. 我想我已经开始逐级改变了我写题解的目的了，不再是为了自己的复习或者巩固，学的再好也会忘记,只落得悲伤与痛苦了，而是为了能够真正介绍知识给大家了，一个人的意志很薄弱，而人民的力量是无限的。
  5. 作者不可能介绍到所有前置知识，部分还得自行根据需要查询相关资料,因此需要有一定基础的人阅读本文
  6. 一切都将逝去，唯有修涵永生。

契约

  1. (N^i)$表示注释$i
  6. l[x]$表示二叉树中，$x$的左儿子，同样的道理可以定义$r[x]
  9. 图论的时间复杂度分析中，默认n表示点数，m表示边数
  10. 部分二元组(u,v)默认表示u连向v的一条边
  11. 部分三元组(u,v,w)默认表示表示u连向v的边权为w的边
  12. 接下来所有的套路都是在无重边的基础之上，因为重边你可以特判掉，选最小的那条即可。

朱刘算法

  1. 考虑树形图的性质，每个点都有唯一的入边（根节点除外，以后讨论入边，都不考虑根节点），于是我们提出这样一个算法，强制选择每个点边权最小的入边，这样如果不存在环，我们肯定得到了最小的树形图。
  2. 考虑如何处理环，有一条性质，因为这个环是由最小的入边所形成的环，因此存在一棵最小树形图，只缺少了环上的一条边，而且缺少的这条边所指向的点的入边必在该棵最小树形图上(N^1)。
  3. 我们想要这个环缩成一个点cnt，而且要表现环上的每条边选与不选，对于进入环上的每条边(u,v,w),v为环上的点,u非环上的点，令w-=in[v]，然后v=cnt，答案强制选上环上的边权，然后删除环上所有的内部连边(N^2),把这个环缩成一个点，递归进行。
  4. 每次形成一个环会至少少一个点，时间复杂度O(nm)。
可以这样考虑证明，假设存在一棵最小树形图$T$,从$T$出发，肯定可以走到环上的某个点，假设走到了$x_0$，此时$x_0$已经有入边了，假设环长$L$,从$x_0$开始，顺时针给环上的点标号$x_0,x_1,x_2,...,x_{L-1}$,此时我们考虑$x_1$,对于$pre[x_1]$,我们可以删掉最小树形图上的$(pre[x_1],x_1)$，连上$(x_0,x_1)$,这样肯定不会变劣答案,可以证明的是，这样得到的还是一棵最小树形图,意味着环上$(x_0,x_1)$的边权等于$in[x_1]$,然后用同样的方法考虑$(x_1,x_2)$,依次类推，我们发现我们环上唯一不能选的边只有$(x_{L-1},x_0)$。 $(N_2)$: 这是一个常见贪心技巧，不知道的人应该仔细理解，自己给出证明。 ## 左偏树 ### 外节点 定义：二叉树中，一个节点没有左儿子或者右儿子就叫做外节点，或者理解为儿子个数小于等于1。 ### 左偏树的距离 定义：在左偏树中，一个节点$x$的子树中，找到深度最大的外节点$y$，那么$dep[y]-dep[x]$就叫做左偏树中$x$到$y$的距离，以后谈距离省略左偏树，特别地空节点距离为$-1$。 ### 左偏树 定义：如果一棵二叉树满足以下性质 1. 二叉堆（以后默认为小根堆进行讨论） 1. 对于任意一个节点$x$，有$d[l[x]]\geq d[r[x]]

我们就把这个二叉树叫做左偏树。

左偏树的性质

  1. d[x]=d[r[x]]+1
  2. 对于任意一个x，d[x]\leq log(n)(n为左偏树的大小)(N_3)
(N_3)

考虑一个节点x，会对哪些节点的距离产生贡献，数学归纳可得，如果他对y产生了贡献，那么y是以满二叉树为基础上建立的二叉树，故y的深度每次减1,sz[y]至少扩大两倍，故得证。

左偏树的操作

  1. 合并:定义函数merge(x,y)为合并以x为根的左偏树和以y为根的左偏树，返回值为新的树根，如果a[x]>a[y]就交换x,y，然后递归进行a[x].r[x]=merge(r[x],y)，此时如果d[l[x]]<d[r[x]]就交换l[x],r[x],最后令d[x]=d[r[x]]+1,return\ x，时间复杂度为log(n),(N_4)
  2. 删除：删除x，直接merge(l[x],r[x])即可，也告诉我们，可以在log(n)的时间复杂度删除树上任意一个节点，前提是找得到。
  3. 加入一个节点，其实把一个节点看作一棵树，就和1一样了。
(N_4)

时间复杂度证明，其实每次递归发现d[x],d[y]其中至少有一个减少了1,因此时间复杂度为O(log(sz[x])+log(sz[y]))，也侧面告诉我们不能启发式合并。

模板

tarjan优化朱刘

算法流程

  1. 朱刘相当于最小生成树中B字开头的算法,而现在介绍的优化，其实相当于prim。
  2. 枚举每个原图中的节点x，然后不停地把边(pre[x],x)加入最小树形图，答案累加in[x]，在某一时刻发现出现了环，删除该环内部所有边，然后暴力把每个指向该环的边(u,v)，令边权减去in[v],然后将这个环缩成一个点,然后迭代进行，直至到达根节点r，这样还是O(nm)。
  3. 考虑优化，我们对于每个点x建一棵左偏树T_x，然后我们就可以在O(1)的时间复杂度查询一个节点的最小入边，缩环的时候直接合并左偏树即可，边权减打标记即可,因此我们需要很好的实现标记下放，一次对环的合并我们不妨及做log(n)，每个节点属于哪个环可以用并查集路径压缩+按秩合并，删除节点可以用延迟删除(N_5)，那么最终时间复杂度不难分析的出来是O(m+nlog(n))。
(N_5)

如果我没记错的话，应该也叫懒惰删除法

参考代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define il inline
#define ri register
#define Size 100050
using namespace std;
int fa[Size],cnt,is[Size];
il int find(int);
il void read(int&),Union(int,int);
struct leftist{
    struct point{
        int l,r,d,v,t,to;
    }a[Size]={{0,0,-1,0,0,0}};
    int r[Size];
    il void merge(int&x,int&y){
        if(!x||!y){x^=y;return;}
        if(a[x].v>a[y].v)x^=y^=x^=y;
        a[y].t-=a[x].t,a[y].v-=a[x].t;
        merge(a[x].r,y);
        if(a[a[x].l].d<a[a[x].r].d)
            a[x].l^=a[x].r^=a[x].l^=a[x].r;
        a[x].d=a[a[x].r].d+1;
    }
    il void spread(int&p){
        a[a[p].l].t+=a[p].t,a[a[p].r].t+=a[p].t;
        a[a[p].l].v+=a[p].t,a[a[p].r].v+=a[p].t;
        a[p].t=0;
    }
    il void pop(int&x){
        spread(x),merge(a[x].l,a[x].r),x=a[x].l;
    }
    il point*top(int&x){
        while(r[x]&&!(find(a[r[x]].to)^x))pop(r[x]);
        if(!r[x])puts("-1"),exit(0);
        a[r[x]].to=find(a[r[x]].to);
        return &a[r[x]];
    }
}L;
int pre[Size];
int main(){
    int n,m,r,ans(0);leftist::point*temp;
    read(n),read(m),read(r),cnt=n,is[r]=r;
    for(int i(1),u,v,w;i<=m;++i)
        read(u),read(v),read(w),
            L.a[i]={0,0,0,w,0,u},
            L.merge(L.r[v],u=i);
    for(int i(1);i<=n<<1;++i)fa[i]=i;
    for(int i(1),j(i);i<=n;j=++i)
        while(!is[j]){
            while(!is[j])
                is[j]=i,j=(temp=L.top(j))->to,
                    ans+=temp->v;if(is[j]^i)break;
            while(~is[j])
                is[j]=-1,j=pre[j]=(temp=L.top(j))->to,
                    temp->t-=temp->v,temp->v=0;++cnt;
            while(is[j]^i)is[j]=i,Union(j,cnt),j=pre[j];
            j=cnt;
        }return printf("%d",ans),0;
}
il void Union(int u,int v){
    if((u=find(u))^(v=find(v)))
        L.merge(L.r[v],L.r[u]),fa[u]=v;
}
il int find(int x){
    return x^fa[x]?fa[x]=find(fa[x]):x;
}
il void read(int&x){
    x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}

扩展知识

  1. 求没有确定的根的树形图:建立一个超级根r，以它为根跑算法,只要将r向原图每个点连接一条权值大于原图中所有边的边权的边，这样选这些边肯定不划算，因此只会选择一条。
  2. 判无解的奇技淫巧:从小到大依次枚举每个点i,加入边(i,(i+1)\%n+1,+\infty),这样如果你最后得到的答案为+\infty，那么就无解了。

写在后面的话

既然你会O(E+nlog(n))，是不是也想谴责luogu为什么放暴力朱刘过了吗？