zoj3201 树形分组背包

很简单的分组背包，不过由于dfs初始化的时候传输组没考虑清楚，wrong了2次，然后用%I64d输出又PE了一次，纠结死了，就像上次做湘潭大学用%lf提交wrong了两个题目一样。。。

ACcode：

#include<cstdio>
#include<cstring>
typedef long long LL;
const int nsize=222;
int n,m,top;
LL dp[nsize],ans;
int v[nsize],w[nsize];
int head[nsize],next[nsize<<1],e[nsize<<1];
void add(int p,int s)
{
next[top]=head[p];
e[top]=s;
head[p]=top++;
}
LL Max(LL a1,LL a2)
{
return a1>a2? a1:a2;
}
void dfs(int rt)
{
LL tp[nsize];
memset(tp,-1,sizeof(tp));
v[rt]=tp[0]=0;
for (int i=head[rt];i!=-1;i=next[i])
{
if (v[e[i]])
{
dfs(e[i]);
for (int j=m;j>0;j--)
{
for (int k=j;k>0;k--)
{
if (tp[j-k]!=-1&&dp[k]!=-1)
tp[j]=Max(tp[j],tp[j-k]+dp[k]);
}
}
}
}
for (int i=1;i<=m;i++)
{
if (tp[i-1]!=-1) dp[i]=tp[i-1]+w[rt];
else dp[i]=-1;
}
ans=Max(ans,dp[m]);
}
int main()
{
int x,y;
while (~scanf("%d %d",&n,&m))
{
top=ans=0;
memset(v,1,sizeof(v));
memset(dp,-1,sizeof(dp));
memset(head,-1,sizeof(head));
for (int i=0;i<n;i++) scanf("%d",&w[i]);
for (int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
add(x,y),add(y,x);
}
dfs(0);
printf("%lldn",ans);
}
return 0;
}

最后

以上就是傻傻酸奶为你收集整理的zoj3201 树形分组背包的全部内容，希望文章能够帮你解决zoj3201 树形分组背包所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。