题目链接:
https://cn.vjudge.net/problem/URAL-1018
题目大意:
给你一棵树,每条边有一个边权,求以1为根节点,q条边的子数(q+1个点),边权和至最大。
解题思路:
dp[root][j], 表示以root为根节点,保留j个节点的最大边权和。
dp[root][j]=max(dp[root][j],dp[root][j-t]+dp[son][t]+len);
t的范围从1到j - 1,因为每个点从dp[][1]开始更新
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 100 + 10; 4 typedef long long ll; 5 struct node 6 { 7 int v, w; 8 node(){} 9 node(int v, int w):v(v), w(w){} 10 }; 11 vector<node>Map[maxn]; 12 int num[maxn];//num[i]表示以i节点为root的子树中的点的数目 13 int dp[maxn][maxn];//dp[i][j]表示以i节点为root的子树中只有j条边最大权值 14 void dfs(int root, int fa) 15 { 16 num[root] = 1; 17 for(int i = 0; i < Map[root].size(); i++) 18 { 19 int v = Map[root][i].v, w = Map[root][i].w; 20 if(v == fa)continue;//不可回溯 21 dfs(v, root);//先将儿子信息更新好 22 num[root] += num[v];//root子树中当前的节点数目 23 for(int j = num[root]; j >= 1; j--)//更新父节点的dp 24 { 25 for(int k = 1; k < j && k <= num[v]; k++)//k不能等于j,k=j时说明root的点数目为0 26 dp[root][j] = max(dp[root][j], dp[root][j - k] + dp[v][k] + w); 27 } 28 } 29 } 30 int main() 31 { 32 int n, k; 33 while(scanf("%d%d", &n, &k) != EOF) 34 { 35 memset(dp, 0, sizeof(dp)); 36 for(int i = 1; i < n; i++) 37 { 38 int u, v, w; 39 scanf("%d%d%d", &u, &v, &w); 40 Map[u].push_back(node(v, w)); 41 Map[v].push_back(node(u, w)); 42 } 43 dfs(1, -1); 44 cout<<dp[1][k + 1]<<endl;//包含k条边,也就是k+1个点 45 } 46 return 0; 47 }