记录编号	58809	评测结果	AAAAA
题目名称	[NOI 1999]最优连通子集	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2013-04-26 21:30:09	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<deque>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int SIZEN=1001;
class NODE{
public:
	int x,y;
	int v;
	int c[5];
	int deg;
	int f;
	NODE(){f=v=deg=0,memset(c,0,sizeof(c));}
	void output(void){
		cout<<x<<" "<<y<<" "<<c[0]<<" "<<c[1]<<" "<<c[2]<<" "<<c[3]<<" "<<c[4]<<endl;
	}
}p[SIZEN];
int n;
bool visit[SIZEN]={0};
void read(void){
	scanf("%d",&n);
	int i,j;
	for(i=1;i<=n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].v);
	for(i=1;i<=n;i++){
		for(j=1;j<i;j++){
			if(abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y)==1){
				p[i].deg++,p[i].c[p[i].deg]=j;
				p[j].deg++,p[j].c[p[j].deg]=i;
			}
		}
	}
}
#define now p[root]
int DFS(int root){
	if(visit[root]) return 0;
	visit[root]=true;
	int i,sum=0;
	for(i=1;i<=now.deg;i++){
		sum+=max(0,DFS(now.c[i]));
	}
	//cout<<root<<" "<<sum<<endl;
	sum+=now.v;
	sum=max(0,sum);
	now.f=sum;
	return sum;
}
int main(){
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	read();
	DFS(1);
	int ans=-1;
	int i;
	for(i=1;i<=n;i++){
		//p[i].output();
		ans=max(ans,p[i].f);
	}
	cout<<ans<<endl;
	return 0;
}