#1272. 【COMP350105期末实验】P8 d-森林

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: JamesHelium

题目描述

说明

本系列题目为 2020 年为计算机试验班 91 开设的 COMP350105 “算法设计与分析” 课程之期末实验题目。 本题目的规定与要求不代表课程实验中的要求,本题目的得分不代表实验得分,本题目的数据也不代表课程期末实验的测试方式。 而且在本 OJ 上的程序正确性、效率性要求往往高于课程得分要求,但代码可读性、程序思想要求却低于课程得分要求。本题目为大家提供严谨的测试,请各位酌情根据自己能力解答。

编程实现T/S 的d 森林问题。 设T 为一带权树,树中的每个边的权都为整数。 又设S 为T 的一个顶点的子集,从T 中删除S 中的所有结点,则得到一个森林,记为T/S。如 果T/S 中所有树从根到叶子节点的路径长度都 不超过d,则称T/S 是一个d 森林。设计一个算 法求T 的最小顶点集合S,使T/S 为一个d 森林。