您的位置:首页 > 博客中心 > 电脑问题 >

AcWing 3760. 最大剩余油量(树的最长路径)

时间:2022-09-07 11:14

题目

一个国家由 n 个城市组成,这 n 个城市由 n?1 条双向道路连接,呈一个树形结构。

每个城市都设有加油站,在第 i 个城市可以购买 wi 升汽油。

汽车在道路上行驶,毫无疑问也会消耗汽油,每条道路的具体耗油量也会给出。

现在,需要制定一条汽车的行进路线,从任意城市 s 出发,经过一条简单路径,到达任意城市 e 结束。

注意,行进路线也可以只包含一个城市(也就是哪都没去)。

汽车初始时油箱是空的,但是可以在路线中经过的每个城市购买汽油,包括开始城市和最终城市。

如果在一条行进路线中,汽车沿一条道路从某一城市开往另一城市时,现有油量小于该条道路所需油量,那么就说明这条行进路线行不通。

请问,在保证行进路线合理的情况下,汽车在抵达最终城市后,可以剩余的最大油量是多少?

再次提醒,汽车在最终城市也可以加油。

输入输出

输入:第一行包含整数 n。

第二行包含 n 个整数 w1,w2,…,wn。

接下来 n?1 行,每行包含三个整数 u,v,c,表示城市 u 和城市 v 之间存在一条双向道路,耗油量为 c。
输出:一个整数,表示可能的最大剩余油量。

思路

这道题是选出一条路径使最大剩余油量最大,即树的最长路径(树的直径)问题。点权为正,边权为负。
可以枚举一条路径的最高点,该点的最长路径由根节点的点权+子树的最长长度+子树的次长长度。用递归来做,递归返回的是子树往下的最长长度,计算出后,更新最长路径长度。写的太混乱了

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 300010;
typedef long long LL;

int tot;
int head[N << 1],ver[N << 1], nxt[N << 1],edge[N << 1];
int w[N];
LL ans;
void add(int u, int v, int c)  // 添加一条边a->b
{
    ver[++tot] = v; nxt[tot] = head[u]; head[u] = tot; edge[tot] = c;
}

LL dfs(int u,int fa){
    LL max1=0,max2=0;   //以u为根节点的子树中最大的长度和次大的长度
    for(int i = head[u];i;i = nxt[i]){
        int v = ver[i];
        if(v == fa) continue;
        LL d = dfs(v,u);    //d是以v为根节点的子树的最长路径
        if(d < edge[i]) continue;
        d -= edge[i];  //走子树到根节点需要耗费油量
        if(d >= max1) max2 = max1,max1 = d; //先更新max2,再更新max1
        else if(d > max2) max2 = d;
    }
    ans = max(ans, max1 + max2 + w[u]);
    return max1 + w[u]; //返回的是以u为根节点的最长路径
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )  cin >> w[i];
    for (int i = 0; i < n-1; i ++ ){
        int u,v,c;
        cin >> u >> v >> c;
        add(u, v, c);
        add(v, u, c);
    }
    dfs(1,0);
    cout << ans;
}

本类排行

今日推荐

热门手游