hdu2196Computer【树形dp】

不念不忘少年蓝@ 2022-09-21 00:29 140阅读 0赞

题目：hdu2196Computer[点击打开链接][Link 1]

题意：给出一颗树，求树中的每个顶点到其他所有顶点的最大值。

类型：树形dp，最短路

分析：题目给出10000个点，否则的话弗洛伊德也是可以跑得，但是给出的是一棵树，那么我们就可以用树形dp了。

首先，我们分析发现，当前一个点的最大距离只有两种来源，一种是它到叶子节点的最大距离，一种是经过根节点的最大距离（也就是根节点到叶子节点**不经过当前点**的最大距离 + 跟到当前点的距离），实现的话发现要求不经过当前点，所以我们求到叶子节点向上的最大距离时还要维护一个次短距离。

首先一遍dfs，求出从任意一个节点到叶子节点的最短路dp【i】【0】和次段路dp【i】【1】，算是一个预处理。

然后，定义状态dp【i】【2】从 i 点出发经过 root 节点的最短路。

状态转移方程 dp【child】【2】 = max（dp【father】【2】，dp【child】【0】+ child.cap==dp【father】【0】？dp【father】【1】：dp【father】【0】）+child.cap；

（PS：另一种方法可以在第一次dfs时把从叶子节点到根节点经过的点标记出来，然后在第二次更新的时候如果遇到是经过的点，然后直接选择次短路，可以尝试一下）

代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <string>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 10100;
    
    struct Node
    {
        int to;
        int cap;
    };
    vector<Node> v[N];
    int dp[N][4]; ///dp[i][0] 为从下往上最短距离 dp[i][1] 为从下往上此短距离 dp[i][2] 为从经过root最短距离
    int n;
    void dfs1(int father)
    {
        int mast=0,maer=0;
        for(int i=0;i<v[father].size();i++)
        {
            Node child=v[father][i];
            dfs1(child.to);
            int cost=dp[child.to][0]+child.cap;
            if(cost>=mast)
            {
                maer=mast;
                mast=cost;
            }
            else if(cost>maer)
            {
                maer = cost;
            }
        }
        dp[father][0]=mast;
        dp[father][1]=maer;
    }
    void dfs2(int father)
    {
        for(int i=0;i<v[father].size();i++)
        {
            Node child=v[father][i];
            dp[child.to][2]=max(dp[father][2],dp[child.to][0]+child.cap==dp[father][0]?dp[father][1]:dp[father][0])+child.cap;
            //dp更新从父节点过来的最大值
            dfs2(child.to);
        }
    }
    int main()
    {
        while(~scanf("%d",&n))
        {
            for(int i=2;i<=n;i++)
            {
                int x,y;
                scanf("%d%d",&x,&y);
                Node tmp;tmp.cap = y;
                tmp.to=i;
                v[x].push_back(tmp);
            }
            Del(dp,0);
            dfs1(1);
            dp[1][2]=0;
            dfs2(1);
            int ans=0;
            for(int i=1;i<=n;i++)
            {
                printf("%d\n",max(dp[i][0],dp[i][2]));
            }
            for(int i=1;i<=n;i++)
                v[i].clear();
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2196