• 树形DP

     树的最长路径【树形DP】  

          题目 树的最长路径【树形DP】icon-default.png?t=M85Bhttps://www.acwing.com/problem/content/description/1074/

    解析 icon-default.png?t=M85Bhttps://www.acwing.com/file_system/file/content/whole/index/content/2826773/

    ​ 

    1. #include
    2. using namespace std;
    3. const int N=1e4+10,M=2*N;
    4. int e[M],ne[M],h[N],idx,w[M];
    5. int f1[N],f2[N];  //用来记录各点路径最大值和次大值
    6. int res;
    7. void add(int a,int b,int c)//邻接表的方式存树
    8. {
    9.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    10. }
    11. void dfs(int u,int f)//该节点和该节点父节点
    12. {
    13.     f1[u]=0,f2[u]=0;   //用来记录最大值和次大值
    14.     for(int i=h[u];~i;i=ne[i])//枚举一遍子树
    15.     {
    16.         int j=e[i];
    17.         if(j==f)continue;//防止循环遍历
    18.         dfs(j,u);//该子树到u
    19.         int m=f1[j]+w[i];//该子树到u的距离
    20.         if(m>=f1[u])f2[u]=f1[u],f1[u]=m;//假如大于最大值，更新一遍最大值和次大值
    21.         else if(m>f2[u]) f2[u]=m;//假如大于次大值，则更新次大值
    22.     }
    23.     res=max(res,f1[u]+f2[u]);//答案求一遍经过该点的最长路径
    24. }
    25. int main()
    26. {
    27.     int n;
    28.     cin>>n;
    29.     memset(h,-1,sizeof h);
    30.     for(int i=1;i
    31.     {
    32.         int a,b,c;
    33.         cin>>a>>b>>c;
    34.         add(a,b,c),add(b,a,c);
    35.     }
    36.     dfs(1,-1);
    37.     cout<
    38. }

    树的中心 

    题目 树的中心icon-default.png?t=M85Bhttps://www.acwing.com/problem/content/description/1075/

    题目 树的最长路径【树形DP】icon-default.png?t=M85Bhttps://www.acwing.com/problem/content/description/1074/

    ​ 

    ​ ​

     

     

    1. #include
    2. using namespace std;
    3. const int N=1e4+10,M=2*N,INF=0x3f3f3f3f;
    4. int e[M],ne[M],h[N],idx,w[M];
    5. int d1[N],d2[N],p1[N],p2[N],up[N];
    6.  
    7. void add(int a,int b,int c)
    8. {
    9.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    10. }
    11. int dfs_down(int u,int f)//返回u的最长向下路径
    12. {
    13.     d1[u]=-INF,d2[u]=-INF;
    14.     for(int i=h[u];~i;i=ne[i])
    15.     {
    16.         int j=e[i];
    17.         if(j==f)continue; //避免向上查找，进入死循环
    18.         dfs_down(j,u);
    19.         int m=d1[j]+w[i];
    20.         if(m>=d1[u])//更新一下最长和第二长的路径，并记录下从该路径是从哪一个点下去的
    21.         {
    22.             d2[u]=d1[u],p2[u]=p1[u];
    23.             d1[u]=m,p1[u]=j;
    24.         }
    25.         else if(m>d2[u]) d2[u]=m,p2[u]=j;
    26.     }
    27.     if(d1[u]==-INF) d1[u]=d2[u]=0;  //如果没有改变过该点的距离，就证明这个点是叶节点
    28.     return d1[u];
    29. }
    30. void dfs_up(int u,int f)  //用父节点更新一下子节点向上的最长路径
    31. {
    32.     for(int i=h[u];~i;i=ne[i])
    33.     {
    34.         int j=e[i];
    35.         if(j==f)continue;
    36.         if(p1[u]==j) up[j]=max(up[u],d2[u])+w[i]; //如果从父节点向下的最长路径进过了要更新的子节点，那么就用第二长的路径更新
    37.         else up[j]=max(up[u],d1[u])+w[i]; //假如不经过自己，则用向上走的最大值更新自己
    38.         dfs_up(j,u);
    39.     }
    40. }
    41. int main()
    42. {
    43.     int n;
    44.     cin>>n;
    45.     memset(h,-1,sizeof h);
    46.     for(int i=1;i
    47.     {
    48.         int a,b,c;
    49.         cin>>a>>b>>c;
    50.         add(a,b,c),add(b,a,c);
    51.     }
    52.     dfs_down(1,-1);//向下走
    53.     dfs_up(1,-1);//向上走
    54.     int ans=INF;
    55.     for(int i=1;i<=n;i++)
    56.     ans=min(ans,max(up[i],d1[i]));
    57.     cout<
    58. }

    数字转换【树形DP】

     题目 数字转换【树形DP】icon-default.png?t=M85Bhttp://ybt.ssoier.cn:8088/problem_show.php?pid=1577

    1. #include
    2. using namespace std;
    3. const int N=5e4+10;
    4. int e[N],ne[N],h[N],idx,w[N];
    5. int sum[N];
    6. bool st[N];//用来标记该点的有父节点
    7. int ans;
    8. void add(int a,int b)
    9. {
    10. 	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    11. }
    12. int dfs(int u)
    13. {
    14. 	int d1=0,d2=0;
    15. 	for(int i=h[u];~i;i=ne[i])
    16. 	{
    17. 		int j=e[i];
    18. 		int m=dfs(j)+1;
    19. 		if(m>=d1)d2=d1,d1=m;
    20. 		else if(m>d2)d2=m;
    21. 	}
    22. 	ans=max(ans,d1+d2);
    23. 	return d1;//返回u为根的最大距离
    24. }
    25. int main()
    26. {
    27. 	int n;
    28. 	cin>>n;
    29. 	memset(h,-1,sizeof h);
    30. 	for(int i=1;i<=n;i++)//求一个数的约数和
    31. 	for(int j=2;j<=n/i;j++)//用类似质数筛的方法
    32. 	{
    33. 		sum[i*j]+=i;//该数加上这个约数
    34. 	}
    35. 	for(int i=2;i<=n;i++)//因为1没有在约了，所以从2开始
    36. 	{
    37. 		if(sum[i]
    38. 		{
    39. 			add(sum[i],i);//把i的父节点令为sum[i]
    40. 			st[i]=true;//标记这个点有父节点
    41. 		}
    42. 	} 
    43. 	for(int i=1;i<=n;i++)
    44. 	{
    45. 		if(!st[i])
    46. 		dfs(i);
    47. 	}
    48. 	cout<
    49. }

    二叉苹果树【有依赖背包DP】

    题目 icon-default.png?t=M85Bhttp://ybt.ssoier.cn:8088/problem_show.php?pid=1575

     

     

    1. #include
    2. using namespace std;
    3. const int N=110,M=2*N;
    4. int n,m;
    5. int h[N],e[M],idx,ne[M],w[M];
    6. int f[N][M];
    7. void add(int a,int b,int c)
    8. {
    9.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    10. }
    11. void dfs(int u,int father)
    12. {
    13.     for(int i=h[u];~i;i=ne[i])//枚举物品组
    14.     {
    15.         if(e[i]==father) continue;
    16.         dfs(e[i],u);
    17.         for(int j=m;j>=0;j--)//体积
    18.             for(int k=0;k//枚举决策
    19.              f[u][j]=max(f[u][j],f[u][j-k-1]+f[e[i]][k]+w[i]);
    20.     }
    21. }
    22. int main()
    23. {
    24.   cin>>n>>m;
    25.   memset(h,-1,sizeof h);
    26.   for(int i=1;i
    27.   {
    28.       int a,b,c;
    29.       cin>>a>>b>>c;
    30.       add(a,b,c),add(b,a,c);
    31.   }
    32.    dfs(1,-1);
    33.    cout<1][m]<//输出第一个根的m个树枝
    34.    return 0;
    35. }

     战略游戏【树形DP+状态机模型】

    题目 战略游戏icon-default.png?t=M85Bhttps://www.acwing.com/problem/content/description/325/

    解析 icon-default.png?t=M85Bhttps://www.acwing.com/solution/content/66365/

    1. #include
    2. using namespace std;
    3. const int N=1510,M=2*N;
    4. int n;
    5. int h[N],e[M],idx,ne[M];
    6. bool st[N];
    7. int f[N][M];
    8. void add(int a,int b)
    9. {
    10.     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    11. }
    12. void dfs(int u)
    13. {
    14.     f[u][0]=0;//表示不放哨兵
    15.     f[u][1]=1;//表示放一个哨兵
    16.     for(int i=h[u];~i;i=ne[i])//枚举子树
    17.     {
    18.         int j=e[i];
    19.         dfs(j);
    20.         f[u][0]+=f[j][1];//当前没哨兵加上子树一定得有哨兵
    21.         f[u][1]+=min(f[j][0],f[j][1]);//当前有哨兵，子树可有可无
    22.     }
    23. }
    24. int main()
    25. {
    26.   while(scanf("%d",&n)!=EOF)
    27.   {
    28.       memset(h,-1,sizeof h);//清空上一次的状态
    29.       idx=0;//清空上一次的状态
    30.       memset(st,0,sizeof st);//清空上一次的状态
    31.       for(int i=0;i
    32.       {
    33.           int a,cnt;
    34.           scanf("%d:(%d)",&a,&cnt);
    35.           while(cnt--)
    36.           {
    37.               int b;
    38.               scanf("%d",&b);
    39.               add(a,b);
    40.               st[b]=true;
    41.           }
    42.       }
    43.   int root=0;
    44.   while(st[root]) root++;//找根节点
    45.   dfs(root);
    46.   printf("%d\n",min(f[root][0],f[root][1]));//输出放或者不放的最小值
    47.   }
    48.    return 0;
    49. }

     皇宫看守【树形DP+状态机模型】

    题目 皇宫看守icon-default.png?t=M85Bhttp://ybt.ssoier.cn:8088/problem_show.php?pid=1579

    解析 icon-default.png?t=M85Bhttps://www.acwing.com/solution/content/66594/

     

     

     

     

    1. #include
    2. using namespace std;
    3. const int N=1510,M=2*N;
    4. int n;
    5. int h[N],e[M],idx,ne[M],w[M];
    6. bool st[N];
    7. int f[N][M];
    8. void add(int a,int b)
    9. {
    10.     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
    11. }
    12. void dfs(int u)
    13. {
    14.     f[u][2]=w[u];//表示放一个哨兵,所花费的费用
    15.     for(int i=h[u];~i;i=ne[i])//枚举子树
    16.     {
    17.         int j=e[i];
    18.         dfs(j);
    19.         f[u][0]+=min(f[j][1],f[j][2]);//当前被父节点看到，则子节点只能自己放或者被子节点的子节点看到，两边取最小
    20.         f[u][2]+=min(f[j][0],min(f[j][1],f[j][2]));//当前有哨兵，则子树三种情况都有可能，取最小
    21.     }
    22.     f[u][1]=0x3f3f3f3f;//因为要求最小值，所以初始化为正无穷
    23.     for(int i=h[u];~i;i=ne[i])//枚举子树
    24.     {
    25.         int k=e[i];
    26.         //这里f[u][0]就是以u根的子树所有f[j][1]与f[j][2]的最小值的和，因为前面更新状态时已经求过
    27.         //所以下面就得减去除第k的f[k][1],f[k][2]的最小值的和，剩下就是状态计算的所求
    28.         f[u][1]=min(f[u][1],f[k][2]+f[u][0]-min(f[k][1],f[k][2]));//表示第k个子树有哨兵，可以看到父节点，其他的只能是要么被儿子看到要么自己也放
    29.     }
    30. }
    31. int main()
    32. {
    33.       cin>>n;
    34.       memset(h,-1,sizeof h);//清空上一次的状态
    35.       for(int i=1;i<=n;i++)
    36.       {
    37.           int a,c,cnt;
    38.           cin>>a>>c>>cnt;
    39.           w[a]=c;
    40.           while(cnt--)
    41.           {
    42.               int b;
    43.               cin>>b;
    44.               add(a,b);
    45.               st[b]=true;
    46.           }
    47.       }
    48.   int root=1;
    49.   while(st[root]) root++;//找根节点
    50.   dfs(root);
    51.   printf("%d\n",min(f[root][1],f[root][2]));//输出被子节点看到或者放的最小值
    52.    return 0;
    53. }

     

  • 相关阅读:
    计算机毕业设计（附源码）python智慧小区团购系统
    腾讯云轻量2核4G5M可容纳多少人访问？
    git的基本使用（一）
    SpringSecurity系列 - 10 传统Web项目表单认证： UsernamePasswordAuthenticationFilter 过滤器
    java毕业设计某市教育局综合信息管理平台mybatis+源码+调试部署+系统+数据库+lw
    MetaAI的融合怪：BlenderBot
    js基础笔记学习52-练习2计算水仙花数1
    测试开发——项目
    使用C语言进行问题分析
    Revit中创建基于线的砌体墙及【快速砌体排砖】
  • 原文地址：https://blog.csdn.net/m0_64378422/article/details/127843813