洛谷——P2015 二叉苹果树

题目连接：https://www.luogu.org/problem/P2015

思路：树形DP入门

/*
每条边有一个权值，保留若干条边，求去掉边后根节点能够到达的所有边的权值和最大是多少
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
int to,nextt,w;
}A[210];
int head[110],se[110],dp[110][110];
int cut,n,m;
void add(int u,int v,int w)
{
A[++cut].to=v;
A[cut].nextt=head[u];
A[cut].w=w;
head[u]=cut;
}
void dfs(int u,int fa)
{
for(int i=head[u];~i;i=A[i].nextt)
{
int v=A[i].to;
if(v==fa) continue;
dfs(v,u);
se[u]+=se[v]+1;
for(int j=min(se[u],m);j>=1;j--)//从后往前dp，否则会发生覆盖问题，类似01背包
{
for(int k=min(j-1,se[v]);k>=0;k--)
{
dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[v][k]+A[i].w);
}
}
}
}
int main()
{
memset(head,-1,sizeof(head));
memset(se,0,sizeof(se));
scanf("%d%d",&n,&m);
int u,v,w;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs(1,-1);
printf("%dn",dp[1][m]);
}

最后

以上就是可爱黄蜂为你收集整理的洛谷——P2015 二叉苹果树的全部内容，希望文章能够帮你解决洛谷——P2015 二叉苹果树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。