HDU 4276 樹形DP The Ghost Blows Light

 題意: 一顆樹有n個結點,每個結點有若干寶物,每條路徑需要若干時間.一個人開始在結點1,問能不能在規定

      的時間T內到達結點n. 若能, 算出他能在規定時間T內最多拿到多少寶物.

分析: 先DFS搜出結點1到結點n的路徑及必過的結點並求出最短時間t,如果t超出T,則無法到達.

      否則, 將必過的路徑摧毀,記下能拿到的寶物數並且總時間減去t, 將必過的結點均作為0的子結點,路徑為0.

      這樣則將樹轉換成以0為根結點. 此時只需求從0點開始在剩余時間(T-t)內最多能拿到多少寶物,普通DP即可.

代碼:

 
#include<iostream>   
#include<cstdio>   
#include<cstring>   
#include<vector>   
  
using namespace std;  
const int maxn=105;  
  
vector<int>Tree[maxn];  
int g[maxn][maxn],val[maxn];  
int dp[maxn][maxn*5];   
bool vis[maxn],vit[maxn][maxn],ok;  
int n,p,m,T,ans;  
void Init(){  
    for(int i=0;i<=n;++i) Tree[i].clear();  
    memset(g,0,sizeof(g));  
    memset(vis,false,sizeof(vis));  
    memset(vit,true,sizeof(vit));  
    ok=true; ans=0;  
}  
//搜索從n->1這條路徑, 並將路徑摧毀, 將必過的結點加到0的子結點, 把寶物值置0   
bool DFS(int cnt,int t){       
    vis[cnt]=true;  
    if(cnt==1){  
        Tree[0].push_back(cnt);                   // 作為0的子結點   
        ans+=val[cnt]; val[cnt]=0;                // 取走寶物, 並置0   
        if(t>=T) ok=false;  
        T-=t;                                     // 空余時間   
        return true;  
    }  
    int len=Tree[cnt].size();  
    for(int i=0;i<len;++i){  
        int son=Tree[cnt][i];  
        if(vis[son]) continue;   
        bool c=DFS(son,t+g[cnt][son]);  
        if(c){  
            vit[cnt][son]=vit[son][cnt]=false;   // 將必過點之間的路徑摧毀, 進行樹的轉換   
            Tree[0].push_back(cnt);              // 作為0的子結點   
            ans+=val[cnt]; val[cnt]=0;           // 取走寶物,並置0   
            return true;  
        }  
    }  
    return false;  
}  
void DFS_DP(int cnt){  
    vis[cnt]=true;  
    int len=Tree[cnt].size();  
    for(int i=0;i<=T;++i)                          //初始化   
        dp[cnt][i]=val[cnt];  
    for(int i=0;i<len;++i){  
        int son=Tree[cnt][i];  
        if(vis[son]||!vit[cnt][son]) continue;  
        DFS_DP(son);  
        int d=g[cnt][son]*2;  
        for(int j=T;j>=d;--j)  
            for(int k=j-d;k>=0;--k)  
                dp[cnt][j]=max(dp[cnt][j],dp[cnt][j-d-k]+dp[son][k]);  
    }  
}  
int main(){  
    while(~scanf("%d%d",&n,&T)){  
        Init();  
        for(int i=1;i<n;++i){  
            int a,b,c; scanf("%d%d%d",&a,&b,&c);  
            g[a][b]=g[b][a]=c;  
            Tree[a].push_back(b);  
            Tree[b].push_back(a);  
        }  
        for(int i=1;i<=n;++i) scanf("%d",&val[i]);  
        DFS(n,0);  
        if(!ok){  
            puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");  
            continue;  
        }  
        memset(dp,0,sizeof(dp));  
        memset(vis,false,sizeof(vis));  
        DFS_DP(0);                               // 從根結點0開始遍歷   
        ans+=dp[0][T];  
        printf("%d\n",ans);  
    }  
    return 0;  
}  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;
const int maxn=105;

vector<int>Tree[maxn];
int g[maxn][maxn],val[maxn];
int dp[maxn][maxn*5]; 
bool vis[maxn],vit[maxn][maxn],ok;
int n,p,m,T,ans;
void Init(){
    for(int i=0;i<=n;++i) Tree[i].clear();
    memset(g,0,sizeof(g));
    memset(vis,false,sizeof(vis));
    memset(vit,true,sizeof(vit));
    ok=true; ans=0;
}
//搜索從n->1這條路徑, 並將路徑摧毀, 將必過的結點加到0的子結點, 把寶物值置0
bool DFS(int cnt,int t){     
    vis[cnt]=true;
    if(cnt==1){
        Tree[0].push_back(cnt);                   // 作為0的子結點
        ans+=val[cnt]; val[cnt]=0;                // 取走寶物, 並置0
        if(t>=T) ok=false;
        T-=t;                                     // 空余時間
        return true;
    }
    int len=Tree[cnt].size();
    for(int i=0;i<len;++i){
        int son=Tree[cnt][i];
        if(vis[son]) continue; 
        bool c=DFS(son,t+g[cnt][son]);
        if(c){
            vit[cnt][son]=vit[son][cnt]=false;   // 將必過點之間的路徑摧毀, 進行樹的轉換
            Tree[0].push_back(cnt);              // 作為0的子結點
            ans+=val[cnt]; val[cnt]=0;           // 取走寶物,並置0
            return true;
        }
    }
    return false;
}
void DFS_DP(int cnt){
    vis[cnt]=true;
    int len=Tree[cnt].size();
    for(int i=0;i<=T;++i)                          //初始化
        dp[cnt][i]=val[cnt];
    for(int i=0;i<len;++i){
        int son=Tree[cnt][i];
        if(vis[son]||!vit[cnt][son]) continue;
        DFS_DP(son);
        int d=g[cnt][son]*2;
        for(int j=T;j>=d;--j)
            for(int k=j-d;k>=0;--k)
                dp[cnt][j]=max(dp[cnt][j],dp[cnt][j-d-k]+dp[son][k]);
    }
}
int main(){
    while(~scanf("%d%d",&n,&T)){
        Init();
        for(int i=1;i<n;++i){
            int a,b,c; scanf("%d%d%d",&a,&b,&c);
            g[a][b]=g[b][a]=c;
            Tree[a].push_back(b);
            Tree[b].push_back(a);
        }
        for(int i=1;i<=n;++i) scanf("%d",&val[i]);
        DFS(n,0);
        if(!ok){
            puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
            continue;
        }
        memset(dp,0,sizeof(dp));
        memset(vis,false,sizeof(vis));
        DFS_DP(0);                               // 從根結點0開始遍歷
        ans+=dp[0][T];
        printf("%d\n",ans);
    }
    return 0;
}