poj 1192 最优联通子集 简单dp

    看起来和图相关，其实就是个简单dp，就和取最大连续和一样，只是在一颗树中取……

    有人说是树状dp，我也不知道是不是

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#define INF 1E9
using namespace std;
vector<int> near[1001];
int X[1001],Y[1001];
int value[1001];
int n,ans=-INF;
int now[1001];
int ok[1001];
int dfs(int v)
{
    ok[v]=1;
    now[v]=value[v];
    for(int i=0;i<near[v].size();i++)
    {
        int u=near[v][i];
        if(ok[u])continue;
        dfs(u);
        now[v]+=(now[u]>0?now[u]:0);
        ans=max(ans,now[v]);
    }
}


int main()
{
    scanf("%d",&n);
    int i,j;
    for(i=0;i<n;i++)
    {
        scanf("%d%d%d",&X[i],&Y[i],&value[i]);
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==j)continue;
            if(fabs(X[i]-X[j])+fabs(Y[i]-Y[j])>1)continue;
            near[i].push_back(j);
            near[j].push_back(i);
        }
    }
    dfs(0);
    printf("%d\n",ans);
}