C++[POJ1849]铲雪车问题——树形DP求出树的直径代码咨询

56 阅读 0 评论 37 点赞

我是靠谱客的博主无心香烟，最近开发中收集的这篇文章主要介绍C++[POJ1849]铲雪车问题——树形DP求出树的直径代码咨询，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

[POJ1849]铲雪车问题

时间限制: 1 Sec 内存限制: 128 MB

题目描述

大雪覆盖了整座城市，市政府要求冬季服务部门尽快将一些街道（列在一份清单中）的积雪清除掉以恢复交通。整个城市由许多交叉路口和街道构成，当然任意两个交叉路口都是直接或间接连通的。清单给出了最少的街道，使得这些街道的积雪清除后任意两个交叉路口之间有且仅有一条通路。

冬季服务部门有2辆铲雪车和2名司机，这2辆铲雪车的出发点相同，都位于某个交叉路口。无论街道上有没有积雪，铲雪车每前进一米都要消耗一升燃料。冬季服务部门要求司机在铲除清单上的所有街道的积雪的前提下，消耗燃料最少，铲完后车可以停在任意交叉路口。

输入

第1行：2个整数N,S。（1 < =N < = 100000,1 < = S < =N），N 为交叉路口总数，S为铲雪车出发的路口序号。路口的编号为1～N。

接下来的N-1行为清单上的街道，每一行包含三个用空格隔开的整数A,B,C，表示一条从交叉路口A到交叉路口B的街道，C为该街道的长度。单位为米，1 < = C < =1000

输出

第1行：一个整数，表示铲掉所有积雪所需的最少燃料。

样例输入

5 2 1 2 1 2 3 2 3 4 2 4 5 1

样例输出
6

此题说到底其实一共有多少辆铲雪车都对结果没有影响（原因请读者看完博客后自行思考）

首先我们来考虑只有一辆铲雪车的情况。

想象一下，一辆铲雪车如果要走完所有的树，有许多边肯定是要走两遍的（不理解的话可以画个图走走）

但还有一些边是只用走一遍的。

如图，红色的边走了两遍，绿色的边只走了一遍：

可以这么走：

也可以这么走：

因为所有的边都必需要走到（包括绿色的边），所以我们不妨用一个变量 $sum$ 来表示所有边的权值的和乘2，最后的结果就是这个 $sum$ 减去所有绿色的边的权值之和。

因为最终要求的答案是最小的，所以我们要做到的最优策略便是使这些绿色的边的权值之和最大。

不知道你们看到最大的边的权值之和第一反应是什么，但我想到的便是树的直径，刚好满足我们要求的这些绿色边的权值之和。

所以我们的策略便是sum减去树的直径（很简单是吧）

这里注意一下这个树的直径应该是从以节点p（车的起点处）的子树中的直径。

如果不知道怎么求树的直径，可以参考一下这篇博客:https://blog.csdn.net/weixin_44049566/article/details/88551163

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
  
const int N=100010;
#define max(a,b) a>=b?a:b
  
struct node {
    int v,w;
    node() {};
    node(int V,int W) { v=V;w=W; };
};
  
int n,p,f[N],sum,maxx;
vector <node> G[N];
 
void dfs(int u,int fa) {//求树的直径
    for(int i=0,v,w;i<G[u].size();i++) {
        v=G[u][i].v,w=G[u][i].w;
        if(v==fa) continue;
        dfs(v,u);
        maxx=max(maxx,f[u]+f[v]+w);
        f[u]=max(f[u],f[v]+w);
    }
}
int main() {
    cin>>n>>p;
    for(int i=1,u,v,w;i<n;i++) {
        cin>>u>>v>>w;
        sum+=2*w;
        G[u].push_back( node(v,w) );
        G[v].push_back( node(u,w) );
    }
    dfs(p,0);
    cout<<sum-maxx;
}