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

#include<cstdio>
#include<iomanip>
#include<cmath>
using namespace std;
int n,x[1005],y[1005],dp[1005],ans;
int tot,v[2005],ne[2005],head[2005];
inline void add(int a,int b){
    v[++tot]=b;ne[tot]=head[a];head[a]=tot;
}
void dfs(int x,int fa){
    for(int p=head[x];p;p=ne[p]) if(v[p]!=fa) 
    {
        dfs(v[p],x);
        if(dp[v[p]]>0) dp[x]+=dp[v[p]];
    }
}
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,dp+i);
    for(int i=1;i<=n;i++)for(int j=1;j<i;j++)
        if(abs(x[i]-x[j])+abs(y[i]-y[j])==1)
        {   add(i,j);add(j,i);}
    dfs(1,0);
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}