可以用f[i][j]表示递推到第i个节点时保留j个树枝的最优解，决策的时候要么只从某个子树中选取，要么就同时从两个子树中选取，而且如果选择了某个子树中的树枝，那么就必须选择和这个子树相连接的树枝。
#include<stdio.h> #include<string.h> #define MAXD 110 #define MAXM 210 int N, Q, e, first[MAXD], next[MAXM], v[MAXM], w[MAXM], f[MAXD][MAXD]; void add(int x, int y, int z) { v[e] = y, w[e] = z; next[e] = first[x], first[x] = e ++; } void init() { int i, j, k, x, y, z; memset(first, -1, sizeof(first)); e = 0; for(i = 1; i < N; i ++) { scanf("%d%d%d", &x, &y, &z); add(x, y, z); add(y, x, z); } } void dfs(int cur, int fa) { int i, j, n = 0, g[2], num[2]; for(i = first[cur]; i != -1; i = next[i]) if(v[i] != fa) { g[n] = v[i], num[n] = w[i]; ++ n; dfs(v[i], cur); } if(n == 1) { for(i = 1; i <= Q; i ++) f[cur][i] = f[g[0]][i - 1] + num[0]; } else if(n == 2) { f[cur][1] = num[0] > num[1] ? num[0] : num[1]; for(i = 2; i <= Q; i ++) { for(j = 0; j < 2; j ++) if(f[g[j]][i - 1] + num[j] > f[cur][i]) f[cur][i] = f[g[j]][i - 1] + num[j]; for(j = 0; j <= i - 2; j ++) if(f[g[0]][j] + num[0] + f[g[1]][i - 2 - j] + num[1] > f[cur][i]) f[cur][i] = f[g[0]][j] + num[0] + f[g[1]][i - 2 - j] + num[1]; } } } void solve() { memset(f, 0, sizeof(f)); dfs(1, -1); printf("%d\n", f[1][Q]); } int main() { while(scanf("%d%d", &N, &Q) == 2) { init(); solve(); } return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/110415.html原文链接：https://javaforall.net
