[关闭]
@rg070836rg 2015-11-29T18:10:43.000000Z 字数 1023 阅读 1443

算法概论实验七

算法概论实验


  1. 实验七
  2. 实验目的与要求:
  3. 1)掌握树型动态规划方法的基本思想与设计策略。
  4. 1.树中的最大独立集问题
  5. 【问题描述】
  6. 给定一个无回路的无向图(即树),设计一个动态规划算法,求出该图的最大独立集,并输出该集合中的各个顶点值。
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. const int MAXN=100;
  6. vector<int> G[MAXN]; //G[i]表示顶点i的邻接点
  7. int l[MAXN]; //结点层次
  8. int p[MAXN]; //根树
  9. int dp[MAXN]; //dp数组
  10. int sumC[MAXN]; //孩子DP和
  11. int sumS[MAXN]; //孙子DP和
  12. int maxL; //最大层次
  13. int n;
  14. void readTree()
  15. {
  16. int u,v;
  17. cin>>n;
  18. for(int i=0;i<n-1;++i)
  19. {
  20. cin>>u>>v;
  21. G[u].push_back(v);
  22. G[v].push_back(u);
  23. }
  24. }
  25. void dfs(int u,int fa)
  26. {
  27. int d=G[u].size();
  28. l[u]= (fa==-1)? 0: (l[fa]+1);
  29. if(l[u]>maxL)
  30. {
  31. maxL=l[u];
  32. }
  33. for(int i=0;i<d;++i)
  34. {
  35. int v=G[u][i];
  36. if(v!=fa)
  37. {
  38. dfs(v,p[v]=u);
  39. }
  40. }
  41. }
  42. int rootDp(int u)
  43. {
  44. //构造u根树
  45. p[u]=-1;
  46. maxL=-1;
  47. dfs(u,p[u]);
  48. for(int i=maxL;i>=0;--i)
  49. {
  50. for(int j=0;j<n;++j)
  51. {
  52. if(l[j]==i)
  53. {
  54. if (sumS[j]+1>sumC[j])
  55. {
  56. dp[j]=sumS[j]+1;
  57. }
  58. else
  59. dp[j] = sumC[j];
  60. if(i-1>=0)
  61. {
  62. sumC[p[j]]+=dp[j];
  63. }
  64. if(i-2>=0)
  65. {
  66. sumS[p[p[j]]]+=dp[j];
  67. }
  68. }
  69. }
  70. }
  71. return dp[u];
  72. }
  73. int main()
  74. {
  75. readTree();
  76. int res=-1;
  77. //分别以每个顶点为根
  78. for(int i=0;i<n;++i)
  79. {
  80. memset(sumS,0,sizeof(sumS));
  81. memset(sumC,0,sizeof(sumC));
  82. int tmp;
  83. if((tmp=rootDp(i))>res)
  84. res=tmp;
  85. }
  86. cout<<res<<endl;
  87. return 0;
  88. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注