P2015 二叉苹果树 树形dp 01背包

P2015 二叉苹果树

题目链接

题意：
给一棵树，每个边都有权值，选择一些边删除，剩余m条边。问删除后所有变得权值和最大是多少？
树形dp 01背包问题；
dp数组：dp[maxn][maxn] ；
dp[x][i] 代表x为根节点的子树上有i条边的最大权值；
转移方程：
num[x]为子树上目前有多少边，为什么说目前呢？ 因为子节点还没遍历完，

for (int j = min(m,num[x]); j > 0; j -- )
for (int k = 0; k <= min(j - 1,num[v]); k ++ )
dp[x][j] = max(dp[x][j],dp[v][k] + dp[x][j - k - 1] + t.second);

因为如果最后剩余的有v这个子树上的边的话，那么x节点与v节点之间的边肯定不能删，所以就是j-k-1；然后再加上这条边。
我还是想不到dp数组能代表点啥。还是菜了；
上代码:

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
typedef pair<int,int> PII;
const int maxn = 105;
vector<PII> vv[maxn];
int dp[maxn][maxn];//dp[x][i] 表示x的字数上保留i条边得到的权值最大值 
int num[maxn];
int m;
void dfs(int x,int f)
{
num[x] = 0;
for (int i = 0; i < vv[x].size(); i ++ )
{
PII t = vv[x][i];
if(t.first == f)
continue;
dfs(t.first,x);
int v = t.first;
num[x] += num[v] + 1;
for (int j = min(m,num[x]); j > 0; j -- )
{
for (int k = 0; k <= min(j - 1,num[v]); k ++ )
{
dp[x][j] = max(dp[x][j],dp[v][k] + dp[x][j - k - 1] + t.second);
}
//
printf("%d ",dp[x][j]);
}
//
printf("n");
}
//	printf("n %d %d n",m,x);
}
int main()
{
int n;
scanf("%d%d",&n,&m);
for (int i = 1; i < n; i ++ )
{
int x,y,val;
scanf("%d%d%d",&x,&y,&val);
vv[x].push_back(make_pair(y,val));
vv[y].push_back(make_pair(x,val));
}
dfs(1,0);
printf("%dn",dp[1][m]);
}

最后

以上就是勤奋曲奇为你收集整理的P2015 二叉苹果树 树形dp 01背包的全部内容，希望文章能够帮你解决P2015 二叉苹果树 树形dp 01背包所遇到的程序开发问题。

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