简单树形DP
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 using namespace std; 7 #define INF 0xfffffff 8 int dp[110][110]; 9 int n,q,ch[110][3]; 10 int p[110][110]; 11 int dfs(int pre,int u,int s) 12 { 13 int i; 14 if(dp[u][s]!=-1) 15 return dp[u][s]; 16 int o = 0,cc[4]; 17 for(i = 1; i <= n ; i++) 18 { 19 if(i==pre) 20 continue; 21 if(p[u][i]) 22 { 23 o++; 24 cc[o] = i; 25 } 26 } 27 if(s==0||o==0) 28 return dp[u][s] = 0; 29 if(o==0&&s>0) 30 return -INF; 31 if(o==1) 32 { 33 dp[u][s] = p[u][cc[1]]+dfs(u,cc[1],s-1); 34 return dp[u][s]; 35 } 36 dp[u][s] = max(p[u][cc[1]]+dfs(u,cc[1],s-1),p[u][cc[2]]+dfs(u,cc[2],s-1)); 37 for(i = 1 ; i < s ; i++) 38 { 39 dp[u][s] = max(p[u][cc[1]]+dfs(u,cc[1],i-1)+p[u][cc[2]]+dfs(u,cc[2],s-i-1),dp[u][s]); 40 } 41 return dp[u][s]; 42 } 43 int main() 44 { 45 int i,u,v,w; 46 memset(dp,-1,sizeof(dp)); 47 scanf("%d%d",&n,&q); 48 for(i = 1; i < n ; i++) 49 { 50 scanf("%d%d%d",&u,&v,&w); 51 p[u][v] = w; 52 p[v][u] = w; 53 } 54 int ans = dfs(-1,1,q); 55 printf("%d ",ans); 56 return 0; 57 }