HDU4276 The Ghost Blows Light（树形DP+背包）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAXN 111
 6 struct Edge{
 7     int v,w,next;
 8 }edge[MAXN<<1];
 9 int NE,head[MAXN];
10 void addEdge(int u,int v,int w){
11     edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
12     head[u]=NE++;
13 }
14 int n,t,val[MAXN],d[MAXN][555],par[MAXN],weight[MAXN];
15 bool dp(int u){
16     bool flag=0;
17     d[u][0]=val[u];
18     for(int i=head[u]; i!=-1; i=edge[i].next){
19         int v=edge[i].v;
20         if(v==par[u]) continue;
21         par[v]=u;
22         weight[v]=edge[i].w;
23         if(dp(v)){
24             flag=1;
25             continue;
26         }
27         for(int j=t; j>=0; --j){
28             for(int k=0; ; ++k){
29                 if(edge[i].w*2+k>j) break;
30                 if(d[v][k]==-1 || d[u][j-edge[i].w*2-k]==-1) continue;
31                 d[u][j]=max(d[u][j],d[u][j-edge[i].w*2-k]+d[v][k]);
32             }
33         }
34     }
35     if(u==n) return 1;
36     return flag;
37 }
38 int rec[MAXN],rn,tot;
39 void dfs(int u){
40     if(u!=1){
41         tot+=weight[u];
42         dfs(par[u]);
43     }
44     rec[rn++]=u;
45 }
46 int ans[MAXN][555];
47 int main(){
48     int a,b,c;
49     while(~scanf("%d%d",&n,&t)){
50         NE=0;
51         memset(head,-1,sizeof(head));
52         for(int i=1; i<n; ++i){
53             scanf("%d%d%d",&a,&b,&c);
54             addEdge(a,b,c);
55             addEdge(b,a,c);
56         }
57         for(int i=1; i<=n; ++i) scanf("%d",val+i);
58         memset(d,-1,sizeof(d));
59         dp(1);
60         rn=tot=0;
61         dfs(n);
62         tot=t-tot;
63         memset(ans,-1,sizeof(ans));
64         for(int i=0; i<=tot; ++i) ans[0][i]=d[rec[0]][i];
65         for(int i=1; i<rn; ++i){
66             for(int j=0; j<=tot; ++j){
67                 for(int k=0; k<=tot; ++k){
68                     if(j+k>tot || ans[i-1][j]==-1 || d[rec[i]][k]==-1) continue;
69                     ans[i][j+k]=max(ans[i][j+k],ans[i-1][j]+d[rec[i]][k]);
70                 }
71             }
72         }
73         int res=-1;
74         for(int i=0; i<=tot; ++i) res=max(res,ans[rn-1][i]);
75         if(res==-1) puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
76         else printf("%d\n",res);
77     }
78     return 0;
79 }