可以用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.cn/110415.html原文链接:https://javaforall.cn