自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:02:54，当前版本为作者最后更新于2019-12-02 13:55:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

写在前面的话

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

契约

1. $(N^i)$表示注释$i$
2. $in[x]$表示$x$的入边的最小边权;
3. $pre[x]$表示$x$的入边，边权为$in[x]$的另外一端。
4. $d[x]$表示左偏树中$x$的距离
5. $a[x]$表示左偏树中$x$的点权
6. $l[x]$表示二叉树中，$x$的左儿子，同样的道理可以定义$r[x]$
7. $dep[x]$表示有根树中$x$的深度，$dep[\text{根}]$是$0$还是$1$无所谓
8. $sz[x]$表示有根树中以$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)$。

---

$(N_1)$:

可以这样考虑证明，假设存在一棵最小树形图$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. 二叉堆（以后默认为小根堆进行讨论）
2. 对于任意一个节点$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为什么放暴力朱刘过了吗？