POJ 1192 -最优连通子集 树形DP

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define oo 1000000007
#define MAXN 1005
using namespace std;
struct node
{
      int x,y,c;
}point[MAXN];
int dp[MAXN],t;
vector line[MAXN];
bool used[MAXN];
void dfs(int x)
{
      int i,m=line[x].size();
      vector h;
      dp[x]=0;
      h.clear();
      for (i=0;i=0) dp[x]+=dp[h[i]];
      }
      dp[x]+=point[x].c;
      t=max(t,dp[x]);
      return;
}
int main()
{
      int i,j,n,ans; 
      while (~scanf("%d",&n))
      {
            for (i=1;i<=n;i++)
            {
                  scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].c);
                  line[i].clear();
            }
            for (i=1;i<=n;i++)
               for (j=1;j<=n;j++)
                  if (abs(point[i].x-point[j].x)+abs(point[i].y-point[j].y)==1)
                    line[i].push_back(j);
            memset(used,false,sizeof(used));
            ans=-oo;
            for (i=1;i<=n;i++)
              if (!used[i])
              {
                    t=-oo;
                    used[i]=true;
                    dfs(i);
                    ans=max(t,ans);
              }
            printf("%d\n",ans);
      }
      return 0;
}