d森林问题

来源：百度知道 编辑：UC知道 时间：2024/06/01 06:03:02
设T 是一棵带权树，树的每一条边带一个正权。又设S 是T 的顶点集,T/S 是从树T 中 将S中顶点删去后得到的森林。如果T/S中所有树的从根到叶的路长都不超过d ，则称T/S 是一个d 森林。 (1)设计一个算法求T的最小顶点集S，使T/S是d 森林。(提示：从叶向根移动) (2)分析算法
(2)分析算法的正确性和计算复杂性。 (3)设T中有n 个顶点，则算法的计算时间复杂性应为O(n)。

#include <iostream>
#include <sstream>
using namespace std;

struct TREE
{
int length, dist;
TREE *son, *next, *father;
}tree[1000] = {0};
stringstream ge[1000];
int d;

void buildtree(int root)
{
int dest, wei;
TREE *cur = 0;
while(ge[root] >> dest >> wei)
{
if (root == 0 || &tree[dest] != tree[root].father)
{
if (cur == 0)
tree[root].son = cur = &tree[dest];
else
{
cur -> next = &tree[dest];
cur = cur -> next;
}
tree[dest].father = &tree[root];
tree[dest].length = wei;
buildtree(dest);
}
}
}

int del(TREE *root)
{
TREE *cur = root -> son;
int delsum = 0;
while (cur != 0)
{
delsum += del(cur);
if (cur -> dist + cur -> length > root -> dist) root -> dist = cur -> dist + cur -> length;
cur = cur -> next;
}
if (r