记录编号	116157	评测结果	AAAAA
题目名称	[NOI 1999]最优连通子集	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2014-08-24 18:49:58	内存使用	0.34 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <iterator>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x7ffffff;
//==============struct declaration==============
struct points
{
  int x,y;
  int val;
  bool con(const points rhs) const
  {
    return abs(x-rhs.x)+abs(y-rhs.y)==1;
  }
}point[1010];
//==============var declaration=================
int n;
bool vis[1010];
int f[1010];
int _maxv=-INF;
vector <int> Edge[1010];
//==============function declaration============
void makegraph(int x);
int dp(int x);
//==============main code=======================
int main()
{  
  string FileName="subset";//程序名 
  string FloderName="COGS";//文件夹名 
  freopen((FileName+".in").c_str(),"r",stdin);
  freopen((FileName+".out").c_str(),"w",stdout);
#ifdef DEBUG  
  system(("cp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\standard.cpp C:\\Users\\Administrator\\Desktop\\"+FloderName+"\\submit.txt").c_str());
#endif   
  scanf("%d",&n);
  For(i,1,n)
  {
    scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].val);
    Edge[i].clear();
  }
  memset(vis,false,sizeof(vis));
  memset(f,-1,sizeof(f));
  makegraph(1);
  int k=dp(1);
  printf("%d\n",_maxv);
  return 0;
}
//================fuction code====================
void makegraph(int x)
{
  vis[x]=true;
  For(i,1,n)
    if (!vis[i]&&point[x].con(point[i]))
    {
      Edge[x].push_back(i);
      makegraph(i);
    }
  return ;
}
int dp(int x)
{
  if (f[x]!=-1)
    return f[x];
  int siz=Edge[x].size()-1;
  int sum=0;
  For(i,0,siz)
  {
    int e=Edge[x][i];
    if (dp(e)>0)
      sum+=f[e];
  }
  sum+=point[x].val;
  if (sum>_maxv)
    _maxv=sum;
  return f[x]=sum;
}