记录编号	575521	评测结果	AAAAA
题目名称	[NOI 1999]最优连通子集	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-09-19 21:56:59	内存使用	0.00 MiB

#include<bits/stdc++.h>
#define MXN 1010
using namespace std;
vector<int>b[MXN];
int n,x[MXN],y[MXN],val[MXN],f[MXN],ans=-999999999;
void dfs(int p,int fa)
{//树形DP求解
	f[p]=val[p];//初始化f(p)
	for(int i=0;i<b[p].size();i++)//遍历p的邻接点
	{
		int x=b[p][i];
		if(x==fa)continue;
		dfs(x,p);//递归求解子树
		f[p]=max(f[p],f[p]+f[x]);//更新f(p)
	}
	ans=max(ans,f[p]);
	return;
}
int main()
{
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d%d%d",&x[i],&y[i],&val[i]);
        for(int i=1;i<n;i++)
         for(int j=i+1;j<=n;j++)
            if(abs(x[i]-x[j])+abs(y[i]-y[j])==1)
             b[i].push_back(j) , b[j].push_back(i);//邻接表存图
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
}