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

题目

一个国家由 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;}

相关文章