ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

【牛客小白月赛45】E - 筑巢(树形DP,dfs)

2022年3月5日 700点热度 0人点赞 0条评论

题目链接: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;
}

本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: dfs DP 图论 树形dp
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号