Information Disturbing 【HDU - 3586】【純樹形DP】

題目連結

  題意挺奇怪的，最初的時候還以為是道網絡流的題目，後來想了想，就是求剪去所有葉子節點到根節點的關系的所需最貴的一條邊最小化的題目，挺拗口的不是嗎？

  這道題，想了良多，聽說有用樹形DP+二分來寫的（之後再補上這樣的做法吧），但我不那麼做，我想了想，樹形DP+鍊式前向星也可以寫，剪去非根節點以外的邊，我們所需的價值不就是要麼剪去與父親的邊，要麼就是剪去所有與兒子的邊的權值的總和，是以dp[i][j]存放的是對于i這個節點，我們處理掉它與它的子節點或者父節點關系的最小花費，j的意思是你用j的錢是否可以達成目的，以及達成目的後的最優解，就是j～上限的所需花費可能會是同一個值，然後我定義了個cost[]數組，從葉子節點開始向上傳回，傳回所要消去這号鍊上的節點所需要的最小花費，其中，從葉子節點往上，我們的花費得從最小下限開始，如果低于了最小下限，說明錢不夠，是以得有這樣的判斷。

  初始化問題：這裡的dp[][]得初始化為極大值，INF一開始寫成(long long)1<<63，會WA，改一下，寫成INF=0x3f3f3f3f就過了，我也不知道是什麼原因，下次規範着寫吧，就像前段時間剛學的鍊式前向星一樣（略懂略懂==）。

完整代碼：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef long long ll;
const int maxN=1005;
const ll INF=0x3f3f3f3f;
int N, M, cnt, head[maxN<<1], mx;
ll dp[maxN][maxN];
struct Eddge
{
    int to, next, val;
    Eddge(int a=0, int b=-1, int c=0):to(a), next(b), val(c) {}
}edge[maxN<<1];
void addEddge(int u, int v, int val)
{
    edge[cnt]=Eddge(v, head[u], val);
    head[u]=cnt++;
}
void dfs(int u, int r)
{
    if(u!=1) for(int i=r; i<=mx; i++) dp[u][i]=r;
    ll cost[maxN]={0};
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        int v=edge[i].to, val=edge[i].val;
        dfs(v, val);
        for(int j=1; j<=mx; j++)
        {
            cost[j]+=dp[v][j];
        }
    }
    for(int i=1; i<=mx; i++)
    {
        if(cost[i]==0) continue;
        dp[u][i]=min(dp[u][i], cost[i]);
    }
}
int main()
{
    while(scanf("%d%d", &N, &M) && (N | M))
    {
        memset(head, -1, sizeof(head)); cnt=mx=0;
        for(int i=1; i<N; i++)
        {
            int e1, e2, e3;
            scanf("%d%d%d", &e1, &e2, &e3);
            addEddge(e1, e2, e3);
            mx=max(mx, e3);
        }
        for(int i=1; i<=N; i++)
        {
            for(int j=1; j<=mx; j++)
            {
                dp[i][j]=INF;
            }
        }
        dfs(1, 0);
        int ans=-1;
        for(int i=1; i<=mx; i++)
        {
            if(dp[1][i]<=M) { ans=i; break; }
        }
        printf("%d\n", ans);
    }
    return 0;
}