自动搬运

查看原文

来自洛谷，原作者为

	include13_fAKe 一路坎坷而来，或将随风而去。

搬运于2025-08-24 22:14:11，当前版本为作者最后更新于2023-08-23 11:37:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

以前的 NOI 真的如此简单吗？

题意

给定一颗树，点有点权，求树上连通块的最大权值（可以是连通块的一部分）。

为什么一定是树呢？

题中已经说到，整点集 $V$ 是单整点集，即对于 $V$ 中的任何两个整点， $V$ 中有且仅有一条连接这两点的道路。

这不就是树的性质吗？

思路

树形 dp 模板题。

大多数的树形 dp 都是从叶向根更新、传值，这道题也不例外。

此题给出的是一棵无根树，但我们可以以 $1$ 结点为根。

设 $dp_u$ 表示在以 $u$ 为根的子树中找到的包含 $u$ 结点的所有连通块的最大权值。

对于所有 $u$ 的子结点 $v$，如果 $dp_v>0$，就让 $dp_u+=dp_v$（不然 $dp_u$ 反而变得更小了）。而 $u$ 结点是必选的，所以不要忘了在 $dp_u$ 中加上结点 $u$ 本身的权值（$C_u$）。

定义函数

$$P(u,v)=\begin{cases}1&(u\text{ 是 }v\text{ 的父结点 })\\ 0&(u\text{ 不是 }v\text{ 的父结点 })\end{cases}$$

将转移方程式写成 $\KaTeX$ 公式，就是这样的：

$$dp_u=C_u+\sum\limits_{i=1}^{n}\max(dp_v,0)\times P(u,v) $$

最终答案就是 $\max dp_i$ 了。

接下来就可以认真做题了。

注意事项

• $dp$ 数组的初值应该赋为 $-\infty$，因为 $C_i$ 可能为负。
• $dp_1$ 的值不一定是 $dp$ 数组中最大的。
• 由于 $n \le 10^3$，数据范围较小，所以可以通过枚举整点集 $V$ 中每个点对是否相邻即可，无需对点集排序。$n^2$ 的时间复杂度没有任何问题。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int n;
int x[N],y[N],c[N];
bool vis[N];
int dp[N];
vector<int> g[N];
void dfs(int u){
	vis[u]=true;
	dp[u]=c[u];
//	cout<<u<<endl;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(!vis[v]){
			dfs(v);
			if(dp[v]>0)	dp[u]+=dp[v];
		}
	}
	return;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j){
				if(abs(x[i]-x[j])+abs(y[i]-y[j])==1){
					g[i].push_back(j);
				}
			}
		}
	}
	dfs(1);
	int ans=INT_MIN;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i]);
//		cout<<dp[i]<<endl;
	}
	cout<<ans<<endl;
	return 0;
}