题目链接:E-筑巢_牛客小白月赛45 (nowcoder.com)
具体题意见原题。
思路
首先观察一下题目,这里的图是一棵树,有N - 1条边,说明整个图是一个连通图,每个点都直接相连或间接连通。
而且这里的边和点权值可以为负数,所以我们应该考虑,先更新叶子节点,再往上更新。
但是叶子节点不太好找,有关系吗?没有关系。
我们可以通过dfs,对树进行遍历,假如现在是节点x,下一个是p,那么就更新完p后更新节点x。在dfs拓展时记录下父节点,防止往回拓展。
既然是DP,那么就有状态转移方程:w[x] = max(w[x], w[x] + w[p] + d[x][p]);
最后遍历1 ~ N节点找出最大值即可,因为最大值并不一定是根节点,可能在中间断开了一下,导致最大值在树枝上。
代码
/* Copyright (C) 2022 ErikTse */ #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <bitset> #include <queue> #include <utility> #include <stack> #include <algorithm> #define pb push_back #define fi first #define se second #define pr printf #define sc scanf #define gc getchar #define int long long//注意使用%lld输出long long类型数据 using namespace std; inline int readInt(){//快速读入int int s = 0,w = 1;char c = gc(); while(c > '9' || c < '0')w = (c == '-' ? -1 : 1),c = gc(); while('0' <= c && c <= '9')s = s * 10 + c - '0',c = gc(); return s * w; } inline string readString(){//快速读入string string s;char c = gc(); while(c == ' ' || c == '\n' || c == '\r')c = gc(); while(c != ' ' && c != '\n' && c != '\r')s += c,c = gc(); return s; } /*-------全局变量------*/ const int maxn = 4e5 + 10,inf = 1e15; int n; struct Edge { int x, w;//到x,舒适度为w }; vector<vector<Edge> > g;//邻接表 int w[maxn]; /*-----自定义函数------*/ inline void dfs(int f,int x)//f表示x的父节点 { for(auto i : g[x]) { if(i.x == f)continue;//如果拓展的点是父节点跳过。 dfs(x, i.x);//更新x的儿子 w[x] = max(w[x],w[x] + w[i.x] + i.w);//儿子更新完成后更新x的舒适度 } } signed main() { //freopen("in.txt","r",stdin); n = readInt(); g.resize(n + 1); for(int i = 1;i <= n; ++ i)w[i] = readInt(); for(int i = 1;i <= n - 1; ++ i) { int x = readInt(), y = readInt(), v = readInt(); g[x].pb({y,v}); g[y].pb({x,v}); } dfs(0, 1); pr("%lld\n",*max_element(w + 1, w + 1 + n)); return 0; }
Comments NOTHING