算法合集之《一些与树有关的题目-》_第1页
算法合集之《一些与树有关的题目-》_第2页
算法合集之《一些与树有关的题目-》_第3页
算法合集之《一些与树有关的题目-》_第4页
算法合集之《一些与树有关的题目-》_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

树乐园——一些与树相关题目

栗师1/10讲题目标重点针对树中动态规划讲题。体会动态规划在树这个特殊模型下思想。同时，也包括到了一些其它算法。因为树优美性，使得各式各样算法都有了发挥余地。2/10题目1给定一棵有n个节点有根树，节点从1到n标号，不一样点标号不一样。对于每一个节点，求在它子孙节点中，有多少个节点标号比它标号小。3/10问题2给定一个有n个节点树，节点从1到n标了号。现在，给每一个点一个w值，w值范围是1到m，而且满足，假如两个节点i,j含有相同w值，那么，在从i节点到j节点唯一一条最短路径上，全部节点(除了i,j)w值都大于iw值(也就是jw值)。现在，要给出一个方案，使得这个方案w值最小。4/10问题3某国有n个城市，这n个城市之间有n-1条高速公路，每一条高速公路连接两个城市，而且经过这些高速公路，任意两个城市都能够相互抵达。现在，消防部队要在这个国家建立若干个消防站，一个消防站建立在某一个城市中。假如某个城市发生火灾，那么距离这个城市最劲消防站将会调动消防部队到火灾城市，假设每一条高速公路都需要花费一单位时间。为了安全，消防部队必须在M时间内抵达火灾城市，请问，最少需要建立多少个消防站？5/10问题4把上面题目扩展一下：1、假如走完每一条高速公路需要花费时间不一样，需要最少消防站是多少？2、在1基础上，假如每一个城市建立一个消防站都有一些费用，那么，最少需要用多少费用才能确保安全？6/10问题5给定一棵有n个节点树，以及定义在边上权值w，选出一个最多有p个节点集合S。定义d[i]=min{dis[i,j],j是S中节点}，要求这么S，使得给定d[1]+d[2]+……+d[n]最小。7/10问题6给定一棵树，以及定义在树上边长度，现在，要问询有多少对节点距离小于等于K。8/10问题7给定一棵树。现在，两个人轮番操作这棵树，他们操作是：从这棵树中删除一条边，这么，树就分成了两个部分，把不包含节点1部分扔掉，只保留含有节点1部分。最终，谁不能这么操作了就算输了。显然，不能操作了就是指只剩下节点1了。9/

人人文库> 全部分类> 办公材料 > 办公文档

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论