谁懂这个算法题?

来源：百度知道 编辑：UC知道 时间：2024/06/25 03:11:50
有个题目。设T 是一棵带权树，树的每一条边带一个正权。又设S 是T 的顶点集,T/S 是从树T 中 将S中顶点删去后得到的森林。如果T/S中所有树的从根到叶的路长都不超过d ，则称T/S 是一个d 森林。 设计一个算法求T的最小顶点集S，使T/S是d 森林。(提示：从叶向根移动)

答案有了，但是笨，读不懂~~大体说是用贪心算法，父亲数组parent表示树；leaf存储叶结点编号。从叶结点向根节点移动。从根节点到叶结点的路长超过d时，将该子树分离。

~说得不明不白的~~怎么个分离法就能得到顶点集呢。哪位大大能大体解释下这个算法的运作细节呢，不一定要把算法用C语言描述，就说明一下思路和步骤，感谢感谢感谢感谢~~

这个问题的最终目的是：对已经给出的带权树T，他的节点分叶节点和根节点两类，S是T的顶点集，也就是说S集合中的顶点可以是根节点和叶节点，现在要把带权树T根据S中的节点来分成多个子树，并且要求分成的多个子树组成为d森林。那这样的节点集合肯定很多了，现在要求的是最少的节点个数，就能达到这一目标。
搞清了题目要求后再对算法进行分析：把带权树T的根节点编号成一个数组parent,叶节点编号成一个数组leaf,由于是带权树，则节点间的权值是已知的，这样我们就可以计算出每个叶节点到根节点的距离，当然如果某个叶节点不是某个根节点的产出，则这个距离是0.这样计算出来到某个节点的距离如果大于d就不行了，得将从这个节点的下级节点分离这颗子树。以保证子树是d树，这样一直到带权树T的总结点结束，这样就把T分离成了d森林。分离的节点集合就是最小顶点集S。

个人看了你的答案，感觉可以用 后根序 遍历法解决。

f(root) = max(f(lchild) + g(lchild), f(rchild) + g(rchild) );
f计算得到的从根到叶的路长
g每一条边带一个正权

如果 f(root) >= d，则当前节点属于 集合S

个人感觉如此

不知……