UVALive 4015 Caves 洞穴（树形DP）

我会带着你远行 2021-12-09 04:21 248阅读 0赞

## 题意：一棵n个节点的有根树，树的边有正整数权，表示两个节点之间的距离，你的任务是回答这样的询问，从根节点出发，走不超过x单位的距离，最多能走多少个节点，节点经过多次算一个，对于每次的询问输出：经过节点数最大的值。 注意题目给出的  i， j，d，其中 j 是 i 的父节点。 ##

## 分析：开始想着dp\[i\]\[x\]表示以i为根节点走x单位距离最多到底的节点数，不太好转移，得转化思路，设 d\[ i \]\[ j \]\[ k \] 表示以第i个节点为根节点的子树机器人访问j个节点走的最少的路程，k==0表示访问完后又回到i节点，k==1 表示访问完后不回来， ##

## 则状态转移方程为： ##

## d\[x\]\[j+k\]\[0\] = min(d\[x\]\[j+k\]\[0\],d\[x\]\[j\]\[0\]+d\[y\]\[k\]\[0\]+len\*2); ##

## d\[x\]\[j+k\]\[1\] = min(d\[x\]\[j+k\]\[1\],min(d\[x\]\[j\]\[1\]+d\[y\]\[k\]\[0\]+len\*2,d\[x\]\[j\]\[0\]+d\[y\]\[k\]\[1\]+len)); ##

## y 表示 x 的儿子，len 表示 x 到 y 的长度。用 son\[ i \] 表示 i 这棵树的节点数。d\[i\]\[1\]\[0\] = d\[i\]\[1\]\[1\] = 0， 每个点到自身的距离均为 0 。接下来就是单独考虑它的子节点了，首先考虑如果返回的话，就一种可能就是：它走其他的子树要返回，然后还要对当前的节点要返回。如果不返回的话，那么它可能走其他的子树要返回，当前的不返回，还有就是当前的子树返回，其他的子树不返回。 枚举 son\[ i \] 时要从大到小，因为这是一维的 0， 1 背包，倒着刷表。 ##

## 参考：[https://blog.csdn.net/u014028317/article/details/45678921][https_blog.csdn.net_u014028317_article_details_45678921]。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int N = 510;
    
    int dp[N][N][2];
    int n,son[N],cnt[N];
    vector <int> g[N];
    
    void dfs(int x) {
        for(int i = 1; i <= n; i++)
            dp[x][i][0] = dp[x][i][1] = inf;
        dp[x][1][0] = dp[x][1][1] = 0;
        son[x] = 1;
        for(int i = 0; i < g[x].size();i += 2) {
            int y = g[x][i],w = g[x][i + 1];
            dfs(y);
            for(int j = son[x];j >0 ; j --) {//这里一定要倒着因为是01背包问题。
                for(int k = 1; k <= son[y]; k++) {
                    dp[x][j + k][1] = min(dp[x][j + k][1],dp[x][j][1]+dp[y][k][1] + w * 2);
                    dp[x][j + k][0] = min(dp[x][j + k][0],min(dp[x][j][0] + dp[y][k][1] + w * 2,dp[x][j][1] + dp[y][k][0] + w));
                }
            }
            son[x] += son[y];
        }
    }
    
    int main() {
        int T = 1;
        while(scanf("%d",&n) != EOF && n) {
            for(int i = 0; i <= n; i++)
                g[i].clear();
            memset(cnt,0,sizeof(cnt));
            for(int i = 1; i < n; i++) {
                int u,v,w;
                scanf("%d %d %d",&u,&v,&w);
                cnt[u]++;
                g[v].push_back(u);
                g[v].push_back(w);
            }
            int root = 0;
            for(int i = 1; i < n; i++)
                if(!cnt[i])
                    root = i;
            dfs(root);
            int q,x;
            scanf("%d",&q);
            printf("Case %d:\n",T++);
            while(q--) {
                scanf("%d",&x);
                int ans = 1;
                for(int i = 1; i <= n; i++)
                    if(dp[root][i][0] <= x)
                        ans = i;
                printf("%d\n",ans);
            }
        }
        return 0;
    }

[https_blog.csdn.net_u014028317_article_details_45678921]: https://blog.csdn.net/u014028317/article/details/45678921