hdu 4276 树形dp

题意：给你n个点，n-1条边构成树，每条边有边权（表示走每条边的时间），每个点有点权，问在时间T从点1走到点n，能够得到最多的点权有多少。

题目链接：点我

由于是树，最优的结果一定经过最短路，其他边要么经过两次，要么零次，所以先求最短路，权置为零（注意最短路上的线一定是只走了一遍的），之后dp，最短路直接搜索即可（树）

其他路一定是经过然后再返回到最短路径上

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 using namespace std;
  9 #define MOD 1000000007
 10 const int INF=1000010;
 11 const double eps=1e-5;
 12 typedef long long ll;
 13 #define cl(a) memset(a,0,sizeof(a))
 14 #define ts printf("*****
");
 15 const int MAXN=1005;
 16 int n,m,tt,tot=0,head[MAXN],dp[MAXN][MAXN],val[MAXN];
 17 int maxw,mint;
 18 struct edge
 19 {
 20     int to,next;
 21     int w;
 22 }edge[MAXN*2];
 23 void addedge(int a,int b,int w)
 24 {
 25     edge[tot].to=a;
 26     edge[tot].next=head[b];
 27     edge[tot].w=w;
 28     head[b]=tot++;
 29 }
 30 void init()
 31 {
 32     memset(head,-1,sizeof(head));
 33     tot=0;
 34     cl(dp);
 35 }
 36 bool dfs1(int u,int pre)
 37 {
 38     if(u==n)    return 1;
 39     for(int i=head[u];i!=-1;i=edge[i].next)
 40     {
 41         int v=edge[i].to;
 42         if(v==pre)  continue;
 43         if(dfs1(v,u))
 44         {
 45             mint+=edge[i].w;
 46             edge[i].w=0;
 47             return 1;
 48         }
 49     }
 50     return 0;
 51 }
 52 void dfs2(int u,int pre)
 53 {
 54     for(int i=0;i<=m;i++)   dp[u][i]=val[u];
 55     for(int i=head[u];i!=-1;i=edge[i].next)
 56     {
 57         int v=edge[i].to;
 58         if(v==pre)  continue;
 59         dfs2(v,u);
 60         int minc=edge[i].w*2;
 61         for(int j=m;j>=minc;j--)
 62         {
 63             for(int k=0;j-k>=minc;k++)
 64             {
 65                 dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k-minc]);
 66             }
 67         }
 68     }
 69 }
 70 int main()
 71 {
 72     int i,j,k;
 73     #ifndef ONLINE_JUDGE
 74     freopen("1.in","r",stdin);
 75     #endif
 76     while(scanf("%d%d",&n,&m)!=EOF)
 77     {
 78         init();
 79         if(n==0&&m==0)  break;
 80         int u,v,w;
 81         for(i=1;i<n;i++)
 82         {
 83             scanf("%d%d%d",&u,&v,&w);
 84             addedge(u,v,w);
 85             addedge(v,u,w);
 86         }
 87         for(i=1;i<=n;i++)
 88             scanf("%d",val+i);
 89         mint=0;
 90         dfs1(1,-1);
 91         if(mint>m)
 92         {
 93             printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!
");
 94             continue;
 95         }
 96         m-=mint;
 97         dfs2(1,-1);
 98         printf("%d
",dp[1][m]);
 99     }
100 }