title: 算法设计与分析实验三：d森林问题
date: 2021-05-19

d森林问题

1. 问题描述
设T为一带权树，树中的每个边的权都为整数。又设S为T的一个顶点的子集，从T中删除S中的所有结点，则得到一个森林，记为T/S。如果T/S中所有树从根到叶子节点的路径长度都不超过d，则称T/S是一个d森林。设计一个算法求T的最小顶点集合S，使T/S为一个d森林。
2. 题目分析
本问题可用贪心算法解。从每个叶子节点向根节点移动，若路途中路长超过d则将子树分离。（1）贪心选择性质：若某一最优解某一步不符合贪心选择，则该步骤得到的子树长度要么和贪心选择得到的相同，要么比贪心选择得到的要短。若相同则贪心选择也可以得到最优解；否则原解不是最优解。（2）最优子结构性质：原树的某一子树删去S中结点（若有）显然也满足森林从根到叶子节点的路径长度都不超过d。
3. 程序设计
数组leaf存储叶节点；数组isCut存储某一结点是否被删去；数组parent存储双亲结点；数组parlen存储某节点到双亲结点的权值；数组dis存储某结点到叶节点的距离.函数cutAndDelete用于问题求解.若当前节点不是根节点,则向上移动,路长超过d且未分离时将结点删除并向根节点移动;若没有超过d则更新dist数组.若出度为0则将该结点添加到叶子节点数组leaf.主函数中先输入并建立树,再调用cutAndDelete求解.
4. 代码

  1. #include "iostream"
  2. #include "fstream"
  3. #include "queue"
  4. using namespace std;
  5. const int maximum = 10000;
  6. int leaf[maximum];
  7. int isCut[maximum];
  8. int parent[maximum];
  9. int parlen[maximum];
  10. int dis[maximum];
  11. int outdeg[maximum];
  12. int cutAndDelete(int n, int d)
  13. {
  14.     int i = 0; int num = 0;
  15.     for (i = 1; i <= leaf[0]; i++)
  16.     {
  17.         if (leaf[i] != 1)
  18.         {
  19.             int p = parent[leaf[i]];
  20.             int len = parlen[leaf[i]];
  21.             if (isCut[p] == 0 && dis[leaf[i]] + len > d)
  22.             {
  23.                 num++;
  24.                 isCut[p] = 1;
  25.                 p = parent[p];
  27.             }
  28.             else if (isCut[p] == 0 && dis[p] < len + dis[leaf[i]])
  29.             {
  30.                 dis[p] = len + dis[leaf[i]];
  31.             }
  32.             if (--outdeg[p] == 0)
  33.             {
  34.                 leaf[++leaf[0]] = p;
  35.             }
  36.         }
  38.     }
  39.     return num;
  40. }
  41. int main()
  42. {
  43.     ifstream input("exp3_in.txt");
  44.     int nodenum, a, i, j, k, n, d, t;
  45.     input >> nodenum;
  46.     for (i = 0; i < nodenum; i++)
  47.     {
  48.         memset(leaf, 0, sizeof(leaf));
  49.         memset(parlen, 0, sizeof(parlen));
  50.         memset(isCut, 0, sizeof(isCut));
  51.         memset(dis, 0, sizeof(dis));
  52.         memset(outdeg, 0, sizeof(outdeg));
  53.         memset(parent, 0, sizeof(parent));
  54.         input >> n >> d;
  55.         for (j = 1; j <= n; j++)
  56.         {
  57.             input >> outdeg[j];
  58.             if (outdeg[j] != 0)
  59.             {
  60.                 for (k = 0; k < outdeg[j]; k++)
  61.                 {
  62.                     input >> t;
  63.                     t += 1;
  64.                     input >> a;
  65.                     parent[t] = j;
  66.                     parlen[t] = a;
  67.                 }
  68.             }
  69.             else if (outdeg[j] == 0)
  70.             {
  71.                 leaf[++leaf[0]] = j;
  72.             }
  73.         }
  74.         int result;
  75.         result = cutAndDelete(n, d);
  76.         cout << result << endl;
  77.     }
  78.     return 0;
  79. }

5. 运行结果
算法设计与分析三：d森林问题 - 图1