zoj3201 树形分组背包

107 阅读 0 评论 71 点赞

我是靠谱客的博主傻傻酸奶，这篇文章主要介绍zoj3201 树形分组背包，现在分享给大家，希望可以做个参考。

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

ACcode：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
}