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操作

最近更新

必备护士述职报告六篇 8页

七年级语文上册第27课《皇帝的新装》 27页

血液透析膜材料抗凝性能研究-全面剖析 35页

运动能源消耗分析-全面剖析 35页

假冒伪劣商品违法活动的特点及整治对策 2页

保温易割冒口在铸钢件上的应用 2页

供热机组利用循环水余热供热技术研究 2页

住房公积金流动性不均衡问题分析及对策 2页

低温快速固化聚酰亚胺环氧F级浸渍漆的研究 2页

《高中生物必修一》4.3物质跨膜运输的方式 21页

优选法在Fp—16龙门铣床上的应用 2页

伊朗雅达油田完井测试作业中沥青质析出分析 2页

企业申请科技成果鉴定的意义及要点研究 2页

火车站扩建项目劳务合同 6页

仪征市国营商业、供销合作社深化改革的思考 2页

以成组技术为基础的CAD数据库的设计 2页

从邯邢铁矿开发谈矿山地质研究 2页

深圳房地产交易合同范本 6页

从我国核电工业发展看技术经济研究 2页

从加拿大造纸技术谈与我国造纸工业有关的几个.. 2页

消防防排烟工程承建合同书版docx 7页

消防器材采购与安装项目施工合同 7页

人类工程学在企业管理中的应用(下) 2页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页

高清地图中国31省市区最全河流水系分布地图建.. 25页

2023年北京市事业单位统考真题及答案 11页

煤矿春季预防性电气试验试措施样板 18页

2025届高考模拟作文“时间管理”升格导写 5页

剑桥雅思原版真题4 114页

《于宏杰-到底神要的是什么呢》 5页