題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4276)
參考鏈接：http://blog.csdn.net/u012841845/article/details/18739425
以及：http://blog.csdn.net/xianxingwuguan1/article/details/18954537
手寫(xiě)鄰接表：http://blog.csdn.net/ooooooooe/article/details/17035501

分析：先尋找1到N的最短路徑和走這段路所用的時(shí)間，再把路徑的權(quán)置為0,如果時(shí)間有多的，就把剩余的時(shí)間拿來(lái)進(jìn)行樹(shù)上背包，具體過(guò)程我已經(jīng)寫(xiě)在了程序的注釋里，之所以要寫(xiě)這個(gè)，是因?yàn)榫W(wǎng)上關(guān)于這道題的文章雖然很多，但都講解得不是很清楚。
head數(shù)組是一種手寫(xiě)鄰接表的方法，在上面的網(wǎng)址可以找到，但是該博并沒(méi)有說(shuō)明，所以我特地去請(qǐng)教了另外的人。它是圖的另一種存儲(chǔ)方法，head[a]表示以a為起點(diǎn)的邊的編號(hào)，下面的add函數(shù)中的head[u] = tol++是在更新編號(hào)(即改為當(dāng)前邊的編號(hào))，表面上看起來(lái)它是在一直變化，但是每一次add它都會(huì)把自己的指存儲(chǔ)在的edge結(jié)構(gòu)體中，這樣就可以根據(jù)一個(gè)head值一直找到它的父親的父親的父親......另外，之所以說(shuō)最短路上的邊指走一遍是因?yàn)樨?cái)寶只有那么多，拿了一次就沒(méi)有了。

include <cstdio>
include <cstring>
include <iostream>
using namespace std;

const int maxn = 200;  
int head[maxn], tol, dpmaxn, weight[maxn], T, t, n;

// 此結(jié)構(gòu)體表示各條邊(這里其實(shí)是把room當(dāng)做是有向無(wú)環(huán)圖來(lái)看待，  
// 每一條邊都以兩個(gè)方向來(lái)表示，該結(jié)構(gòu)體的元素含義如下：  
// next：表示下一條以當(dāng)前邊為起點(diǎn)的邊(和鄰接表的實(shí)現(xiàn)有些類(lèi)似) 
// to：表示這條邊的終點(diǎn)  
// time：表示走這條邊所需要的時(shí)間  
// 另外兩個(gè)就是默認(rèn)構(gòu)造函數(shù)和構(gòu)造函數(shù)了  
struct node  
{  
    int next, to, time;  
    node(){};  
    node(int next, int _to, int _time) : next(next), to(to), time(time){}  
}edge[5*maxn];

// add函數(shù)用來(lái)添加邊(每條邊用edge結(jié)構(gòu)體表示)  
void add(int u, int v, int time)  
{  
    edge[tol] = node(head[u], v, time);  
    head[u] = tol++;  
}

// 深度搜索找到1到N的最短路徑(即花費(fèi)時(shí)間最少)  
// 并把該路徑上的所有邊所要的時(shí)間置為0，方便之后搜索，并得到最短時(shí)間為t  
// 其中u表示當(dāng)前節(jié)點(diǎn)，pre表示上一個(gè)節(jié)點(diǎn)  
bool dfs(int u, int pre)  
{  
    if(u == n)  
        return 1;  

    for(int i = head[u]; i != -1; i = edge[i].next)  
    {  
        int v = edge[i].to;  
        if( v == pre )  
            continue;  

        if(dfs(v, u)) // 當(dāng)返回1時(shí)就表示采取了那一條邊  
        {  
            t += edge[i].time;  
            edge[i].time = 0;  
            return 1;  
        }  
    }  
    return 0;
}

// 深度搜索，統(tǒng)計(jì)了所有節(jié)點(diǎn)在一定時(shí)間范圍內(nèi)所有時(shí)間所能獲得的最大價(jià)值  
// dpu：表示從u點(diǎn)出發(fā)到回到u點(diǎn)，花費(fèi)時(shí)間j所能獲得的最大的財(cái)富  
void dfs1(int u, int pre)  
{  
    for(int i = 0; i <= T; i++) // T為剩下的總時(shí)間  
        dpu = weight[u]; // 只要是經(jīng)過(guò)了這個(gè)節(jié)點(diǎn)的都應(yīng)該把它的財(cái)寶即weight加起來(lái)  

    for(int i = head[u]; i != -1; i = edge[i].next) // 這就是上面使用鄰接表的作用，方便深度搜索  
    {  
        int v = edge[i].to;  
        if( v == pre ) // 如果是指向上一條邊的就直接略過(guò)  
            continue;  
        dfs1(v, u); // 遞歸       
        int pp = 2*edge[i].time; // 與u點(diǎn)直接相連的那一條邊的時(shí)間，因?yàn)槿绻^續(xù)下去，就必然會(huì)經(jīng)過(guò)該邊  
        for(int j = T; j >= pp; j–) // j必須大于走那條邊的時(shí)間，它表示的是從該邊走的總時(shí)間  
            for(int k = 0; k <= j-pp; k++) // k表示走了那條邊后從那條邊的終點(diǎn)繼續(xù)走所用的時(shí)間  
                dpu = max(dpu, dpv+dpu); // j-pp-k表示剩下的從u點(diǎn)出發(fā)走的時(shí)間  
    }  
}

int main()  
{  
    int i, j, k, p;  
    while(~scanf(“\%d\%d”, &n, &T))  
    {  
        memset(head, -1, sizeof(head));  
        tol = 0;  
        for(i = 1; i < n; i++)  
        {  
            scanf(“\%d\%d\%d”, &j, &k, &p);  
            add(j, k, p);  
            add(k, j, p);  
        }  
        for(i = 1; i <= n; i++)  
            scanf(“\%d”, &weight[i]);  
        t = 0;  
        dfs(1, 1);  
        if(t > T)  
        {  
            puts(“Human beings die in pursuit of wealth, and birds die in pursuit of food!”);  
            continue;  
        }  
        memset(dp, 0, sizeof(dp));  
        T -= t;  
        dfs1(1, -1);  
        cout<< dp1 <<endl; // 應(yīng)該無(wú)論是否從1出發(fā)都能得到同樣的結(jié)果的  
    }  
    return 0;  
}

這道題花了兩天時(shí)間，寫(xiě)了七八張紙都沒(méi)有完全理解清楚，難道真的是我太愚笨了嗎？