HDU 4276 树形dp + 背包 - c++编程基础

题意：

n 个点 maxtime的时间

下面给定一棵树及走过该边需要的时间

最后一行给定每个点的宝藏价值

问在maxtime时间内能否从 1->n ，若能输出最多能获得的宝藏价值

思路：

对于树，除了1->n的路径，若去其他点则要走回头路

所以我们可以先走到终点，最后时间 - 1-n路径花费的时间，再把该路径的边花费改为0

这样就是剩下时间，走非路径上点能获得的最高价值，就是背包问题

dp[i][j] 表示 i 点用了 j 时刻能获得的最大价值

先用spfa跑出1-n的路径，再修改路径上的边权，树形背包一下结果就是 dp[1][maxtime]

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define inf 10000000  
#define L(x) (x<<1)  
#define R(x) (x<<1|1)  
#define Mid(x,y) ((x+y)>>1)  
#define ll int  
using namespace std;  
inline ll Min(ll a,ll b){return a>b b:a;}  
inline ll Max(ll a,ll b){return aq;  
    q.push(1);  
    memset(dis, -1, sizeof(dis));  
    dis[1] = 0;  
    pre[1] = -1;  
    while(!q.empty()){  
        int u = q.front(); q.pop();  
        for(int i = head[u]; i !=-1;i = edge[i].nex){  
            int v = edge[i].to;  
            if(dis[v] == -1)  
            {  
                dis[v] = dis[u] + edge[i].dis;  
                pre[v] = u;  
                q.push(v);  
            }  
        }  
    }  
}  
int dp[N][505];  
void dfs(int u, int fa){  
    for(int i = 0;i <= maxtime; i++)dp[u][i] = a[u];  
    for(int i = head[u]; ~i; i =edge[i].nex)  
    {  
        int v = edge[i].to;  
        if(v != fa)  
        {  
            dfs(v, u);  
            int cost = edge[i].dis<<1;  
            for(int j = maxtime; j>




= cost; j--)  
            {  
                for(int k = 0; k<= j - cost; k++)  
                    dp[u][j] = Max(dp[u][j], dp[v][k] + dp[u][j-cost-k]);  
            }  
        }  
    }  
}  
bool Islian[N];  
  
int main(){  
    ll i, u, v, d, j;  
  
    while(~scanf("%d %d",&n,&maxtime)){  
        memset(Islian, 0, sizeof(Islian));  
        memset(head, -1, sizeof(head)); edgenum = 0;  
        memset(dp, 0, sizeof(dp));  
  
        for(i=1;imaxtime)  
        {printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");continue;}  
        i = n;  
        while(i!=-1)  
        {  
            Islian[i] = true;  
            i = pre[i];  
        }  
        i = n;  
        while(i!=-1)  
        {  
            for(j=head[i];j!=-1;j=edge[j].nex)  
                if(Islian[ edge[j].to ])  
                    edge[j].dis = 0;  
            i = pre[i];  
        }  
  
        maxtime -= dis[n];  
        dfs(1,-1);  
        printf("%d\n",dp[1][maxtime]);  
    }  
    return 0;  
}