已阅读5页,还剩7页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
树的最大连通 分支问题,问题描述:,给定一棵树T,树中每个顶点u都有一个权w(u),权可以是负数。现在要找到树T的一个连通子图使该子图的权之和最大。,对于给定的树T,编程计算树T的 最大连通分支。,编程任务:,第1行有1个正整数n,表示树T有n个顶点。 树T的顶点编号为1,n。 第2行有n个整数,表示n个顶点的权值。 接下来的n-1行中,每行有表示树T的一条 边的2个整数u,v,表示顶点u与顶点v相连。,数据输入:,由文件input.txt给出输入数据。,结果输出:,将计算出的最大连通分支的权值输出 到文件output.txt。,input.txt: 5 -1 1 3 1 -1 4 1 1 3 1 2 4 5,输入文件示例:,1,2,3,4,5,-1,3,1,-1,1,最大连通分支 连通图 连通图中各结点的权值之和最大,输出文件示例:,output.txt: 4,1,2,3,4,-1,3,1,1,树根,root,T1,T2,W0,W0,最大连通分支在子树或树中,因此对树进行遍历,依次求出以每个结点为树根的最大连通分支权值。,Wr=Wr+Wt1,root,T1,T2,W0,W0,算法分析:,问题具有两个子性质:,最优子结构性质 子问题重叠性质,树根,root,T1,T2,W0,W0,算法实现:,1,2,3,4,5,3,1,-1,1,树根,-1,对于叶子结点或儿子个数为0的 结点,其最大连通分支权值为该 结点的权值 某一结点的最大连通权值0, 则将其值加到它的父亲结点的最 大连通权值,反之舍弃该值 最后求出根结点的最大连通权 值,结束遍历 所求最大连通分支权值即结点中 的最大连通权值,数据结构,struct Cnode long weight; /结点的权值 int father; /该结点的父亲结点 int childnum; /结点的儿子数 long wMax; /结点的最大连通分支的权值 bool visited; /该结点是否被访问过 ;,动态创建数组表示树 Cnode *tree=new Cnoden+1; 存储记录初始化及数据输入 for (i=1;i(treei.weight);,算法步骤(1),for (i=1;iuv; treev.father=u; treeu.childnum+; ,treei.wMax=treei.weight; ,确定树根 for (i=1;i0 for (i=1;i0) treetreei.father.wMax=treetreei.fat
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年江苏南通海安高级中学高二上10月月考化学试卷含答案
- 2025选调生考试申论刷题宝典及答案
- 2025理财规划师理财规划基础考前模拟及答案
- 2025基金从业资格证券投资基金基础知识能力提升题及答案
- 2025初级统计师统计实务真题演练题及答案
- 2025一级建造师建设工程法规及相关知识全科综合及答案
- 2026年徐州市中考道德与法治试卷(含答案)
- 通知财务预算调整事项函5篇范本
- 城市更新项目延期风险管理指南
- 化工设备安全维护规程
- 中国中煤能源集团有限公司2027届秋季校园招聘笔试备考试题及答案解析
- 医务人员手卫生规范(WS-T313-2019)
- 2026年特种设备安全管理人员(A证)考试练习题库(附答案)
- 2026年安全阀校验作业全真模拟题库及答案
- 2027年江苏省高职单招职业技能考试题库附完整答案详解(考点梳理)
- 减轻外周静脉补钾疼痛方法总结2026
- 水利水电工程施工图审查技术导则(TJWEA 0001-2025)
- 6.2中位数和箱线图第2课时四分位数及箱线图
- 《测绘工程管理与法规》课件-第七单元 测绘法规
- 第一节《光的直线传播》作图题
- 《西方经济学(马工程版)》思考与练习题目
评论
0/150
提交评论