1 / 19
文档名称:

算法合集之《维护森林连通性-动态树》.ppt

格式:ppt   大小:3,262KB   页数:19页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

算法合集之《维护森林连通性-动态树》.ppt

上传人:165456465 2025/3/15 文件大小:3.19 MB

下载得到文件列表

算法合集之《维护森林连通性-动态树》.ppt

相关文档

文档介绍

文档介绍:该【算法合集之《维护森林连通性-动态树》 】是由【165456465】上传分享,文档一共【19】页,该文档可以免费在线阅读,需要了解更多关于【算法合集之《维护森林连通性-动态树》 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。维护森林连通性——动态树
PLEASE ENTER YOUR TITLE HERE
华东师大二附中
陈首元
维护一个森林
01
支持边的插入与删除
02
支持树的合并与分离
03
支持寻找路径上费用最小的边
04
所有操作的均摊复杂度为O(logN)
05
动态树
2
3
4
5
6
7
8
1
10
20
-20
0
30
-5
-5
Root(1,2,3,4,5,6,7,8)=1
MinCost(6)=10
Update(7,10)
5
40
Evert(6)
新树根
Cut(4)
Root(7,8)=4
Link(3,4,10)
Evert(v)使v成为新的根,并将v到原树根上的边反向
Cut(v)删除v与其父节点连接的边
Link(v,w,x)将以v为根的树连接到节点root(w)上,(v,w)的费用为x
Update(v,x)使v到树根路径上的边的费用+x
MinCost(v) 返回v到根路径上费用最小的边
Root(v) 返回包含节点v的树的根
动态树的基本操作
将树中的边分为实边、虚边两种,每个节点最多向其子节点连出一条实边
将树划分为一些完全由实边组成的路径,只对这些路径进行操作
01
02
操作的实现


一条路径
路径的基本操作
Path(v):返回包含v的路径 (每个路径有一个标志)
Head(p),Tail(p):返回首节点、尾节点
Pmincost(p):返回p中费用最小的边
Pupdate(p,x:real):将p中每条边的费用+x
Reverse(p):将p中的每条边反向
Concatenate(p,q,x) :添加边(tail(p),head(q))费用为x,将路径p,q合并
Split(v):将v从路径中删除并把路径分为两部分
Splice
01
Splice(p) :将路径p向更靠近根的方向增长
实现方法:把虚边(tail(P),Parent(p)) 变为实边,为了维护实边的性质,将原来从Parent(P)中连出的边设为虚边
02
Expose
1
Expose(v):将从v到树根路径上的所有边设为实边
实现方法:不断调用splice直到根为止
2
有了Expose(v),就可以实现所有动态树操作了
3
Procedure Link(v,w:vertex;x:real);
01
02
03
04
Begin
Concatenate(path(v),expose(w),x);
End;
Link操作

最近更新

《如何做好客户服务》 42页

人力资源绩效考核结果工作总结汇报 5页

健身房装修合同正规样本 9页

体育用品跨国运输合同-@-1 9页

人力资源管理心理学研究-人力资源论文-管理论.. 5页

交通枢纽石材运输搬运合同 7页

人力资源管理六大模块基本知识整理归纳 5页

人力资源管理中的绩效激励与员工满意度关系研.. 5页

人力资源管理中的员工关系处理技巧 5页

二零二五年度酒店客房租赁及客房设施维护保养.. 10页

人力资源管控在企业管理中的作用 5页

人力资源有限公司管理系统规章制度 4页

人力资源年终总结方案(三) 3页

二零二五年度艺术展览活动服务合同 9页

人力资源公司1-3年规划 3页

二零二五年度美甲行业跨界合作开发合同 10页

事业单位人力资源管理存在的问题及策略 4页

中西管理思想中的人本思想比较 5页

二零二五年度电子产品售后服务网络建设采购合.. 9页

中小企业人才招聘方法研究 4页

中国餐饮连锁企业薪酬管理现状及对策研究--以.. 5页

二零二五年度物流配货与智能驾驶协议 9页

二零二五年度湖南省商品房买卖合同(生态住宅.. 10页

一种单极倍频电压型SPWM软开关DCAC逆变器的设.. 6页

【推荐下载】最新体育类开题报告 6页

【2025-2025】还要感谢同事在我论文写作过程中.. 3页

《浅谈我国中小型民营企业人员的流失与管理80.. 7页

二零二五年度新型绿色厂房租赁合同解除补偿协.. 7页

二零二五年度户外瓷砖销售及安装服务合同集合.. 9页

5、腾讯绩效考核方案设计 4页