HDU4276 The Ghost Blows Light 树形DP - c++编程基础

TOP

HDU4276 The Ghost Blows Light 树形DP

2015-07-24 05:53:52 来源: 作者: 【大中小】浏览:5次

做这个题的时候想到了，先来一遍最短路，判断是否可以到达，若可以减去最短路的花费，再在剩下的花费里进行DP求最优解，想到了但是没做到，很多细节没有处理好，结果崩盘了，唉，看题解很多人都是两边dfs，不过这位大牛也是先spfa了一遍，给我这个弱菜看看刚好，这篇好好记录下来，

最后参考了大牛的：http://blog.csdn.net/acm_cxlove/article/details/7964739，可以说是一模一样了

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #include
               
                 #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector
                
                  > G; //typedef pair
                 
                   P; //vector
                  
                    > ::iterator iter; // //map
                   
                    mp; //map
                    
                     ::iterator p; typedef struct Node { int fro,to; int nex; int val; }; Node edge[100 * 4]; int value[100 + 5]; int head[100 + 5]; bool vis[100 + 5]; int dis[100 + 5]; int father[100 + 5]; int mark[100 + 5]; int dp[100 + 5][500 + 5]; int tot; int n,t; void init() { memset(head,-1,sizeof(head)); memset(value,0,sizeof(value)); memset(edge,0,sizeof(edge)); memset(mark,0,sizeof(mark)); memset(dp,0,sizeof(dp)); tot = 0; } void add(int u,int v,int w) { edge[tot].fro = u; edge[tot].to = v; edge[tot].val = w; edge[tot].nex = head[u]; head[u] = tot++; } void spfa() { for(int i=0;i<=n;i++) dis[i] = inf; dis[1] = 0; memset(vis,false,sizeof(vis)); memset(father,0,sizeof(father)); queue
                     
                       q; int s = 1; q.push(s); vis[s] = true; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u];i != -1;i = edge[i].nex) { int v = edge[i].to; int val = edge[i].val; if(dis[v] > dis[u] + val) { dis[v] = dis[u] + val; father[v] = u; mark[v] = i; if(!vis[v]) { vis[v] = true; q.push(v); } } } } for(int i=n;i != 1;i=father[i]) edge[mark[i]].val = 0; } void dfs(int u,int fa) { for(int i=head[u];i!=-1;i=edge[i].nex) { int v = edge[i].to; int val = edge[i].val * 2; if(v == fa)continue; dfs(v,u); for(int j=t;j>=val;j--) for(int k = j-val;k>=0;k--) dp[u][j] = max(dp[u][j],dp[u][k] + dp[v][j - k - val]); } for(int i=0;i<=t;i++) dp[u][i] += value[u]; } int main() { while(scanf("%d %d",&n,&t) == 2) { init(); for(int i = 1;i < n;i++) { int u,v,w; scanf("%d %d %d",&u,&v,&w); add(u,v,w); add(v,u,w); } for(int i = 1;i <= n;i++) scanf("%d",&value[i]); spfa(); if(dis[n] > t) { puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!"); continue; } t -= dis[n]; dfs(1,0); printf("%d\n",dp[1][t]); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：[BZOJ 2753][SCOI2012]滑雪与时间..	下一篇：dede 如何调用其他栏目的文章或者..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: