首页 > 代码库 > URAL 1108 简单的树形dp背包问题
URAL 1108 简单的树形dp背包问题
题目大意：
一颗苹果树上，每条边都对应了一个权值，最后留下包括root ： 1在的含有 m 条边的子树 , 希望留下的子树中权值之和最大
这里保留m条边，我们可以看作是保留了 m + 1 个点
令dp[u][j] 表示 u 为根的子树中包含了j个点的子树中得到的权值最大和
状态转移方程：
dp[u][j] = max{dp[v][k] + dp[u][j-k] + e[i].d} v为u的子节点 j>k>=1 , 1<=j<=m+1
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int N = 105; 6 int val[N] , first[N] , k , dp[N][N]; 7 8 struct Edge{ 9 int y , next , d;10 }e[N<<1];11 12 void add_edge(int x, int y , int d)13 {14 e[k].y = y , e[k].d = d , e[k].next = first[x];15 first[x] = k++;16 }17 18 void dfs(int u , int fa , int m)19 {20 for(int i = first[u] ; i!=-1 ; i=e[i].next){21 int v = e[i].y;22 if(v == fa) continue;23 dfs(v , u , m);24 for(int j = m ;j>=1; j--)25 for(int k=1 ; k<j ; k++)26 dp[u][j] = max(dp[u][j] , dp[v][k] + dp[u][j-k] + e[i].d);27 }28 }29 30 int main()31 {32 // freopen("a.in" , "r" , stdin);33 int n,m,x,y,d;34 while(scanf("%d%d" , &n , &m)==2)35 {36 memset(first , -1 , sizeof(first));37 k = 0;38 for(int i=1 ; i<n ; i++){39 scanf("%d%d%d" , &x , &y , &d);40 add_edge(x , y , d);41 add_edge(y , x , d);42 }43 44 memset(dp , 0 , sizeof(dp));45 dfs(1 , -1 , m+1);46 47 printf("%d\n" , dp[1][m+1]);48 }49 return 0;50 }
URAL 1108 简单的树形dp背包问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。