很裸的一个树形DP，而且连2叉都不用转。。就是建树有点复杂。
稍微有点不同的地方就是它的值在边上，因为一旦选了某条边，那么一定要选一个父亲一个孩子，而每个孩子只有1个父亲，所以可以把边值直接定为孩子的点值，这样就跟一般的树形DP木有什么区别了。
f[i][j]表示以第i个节点做根，保留j条边的最大放法数，那么有：
f[i][j]=max(f[i][j],f[l][k]+f[r][j-k])
#include<stdio.h>
typedef struct treetype
{
long l,r,z;
}treetype;
treetype tree[101];
long map[101][101];
long a,b,c,n,q,i;
long have[101][101];
long f[101][4];
long max(long a,long b)
{
if (a<b)
return b;
return a;
}
void maketree(long i,long z)
{
long a,b,l,r,c;
if (i==0)
return;
tree[i].z=z;
a=f[i][1];b=f[i][2];c=f[i][3];
if (tree[a].z==-1)
{
tree[i].l=a;
if (tree[b].z==-1)
tree[i].r=b;
else if (tree[c].z==-1)
tree[i].r=c;
}
else
{
if (tree[b].z==-1)
{
tree[i].l=b;
if (tree[c].z==-1)
tree[i].r=c;
}
else
if (tree[c].z==-1)
tree[i].l=c;
}
l=tree[i].l;r=tree[i].r;
maketree(l,map[i][l]);maketree(r,map[i][r]);
}
long dfs(long i,long num)
{
long l,r,ans,ii;
if (i==0)
return 0;
num--;
if (num==0)
return tree[i].z;
if (have[i][num]!=0)
return have[i][num];
ans=0;
l=tree[i].l;r=tree[i].r;
for (ii=0;ii<=num;ii++)
ans=max(ans,tree[i].z+dfs(l,ii)+dfs(r,num-ii));
have[i][num]=ans;
return ans;
}
int main()
{
scanf("%d %d",&n,&q);
for (i=1;i<=n;i++)
tree[i].z=-1;
for (i=1;i<=n-1;i++)
{
scanf("%d %d %d",&a,&b,&c);
f[a][0]++;f[a][f[a][0]]=b;
f[b][0]++;f[b][f[b][0]]=a;
map[a][b]=c;map[b][a]=c;
}
maketree(1,0);
printf("%d",dfs(1,q+1));
}
posted on 2011-06-28 21:31
梦转千寻 阅读(40)
评论(0) 编辑 收藏 引用