学步园

http://blog.csdn.net/birdforever/article/details/5874502

题目中文。。。。但是描述得很复杂。。。不知道为啥要这样，

其实就是一个求无向树的所有子树和的最大值

树形dp

dp[i][0]表示以i为根，不包括i结点的子树获得最大权

dp[i][1]表示以i为根，包括i结点的子树获得的最大权

dp[i][0] = max(dp[k][0], dp[k][1]) k为i的所有孩子结点

dp[i][1] = i结点的权 + dp[k][1] 如果dp[k][1] > 0

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

struct node
{
    int u, next;
};

struct point
{
    int x, y, c;
};

const int maxn = 1010;

int dp[maxn][2], e, n, head[maxn];
bool visited[maxn];
node edge[maxn*10];
point points[maxn];

void addEdge(int u, int v);
void dfs(int u);
int main()
{
    e = 0;
    memset(head, -1, sizeof(head));
    memset(visited, 0, sizeof(visited));
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d %d %d", &points[i].x, &points[i].y, &points[i].c);
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if((abs(points[i].x - points[j].x) + abs(points[i].y - points[j].y)) == 1)
                addEdge(i, j);
        }
    }
    dfs(0);
    printf("%d\n", max(dp[0][0], dp[0][1]));
    return 0;
}

void addEdge(int u, int v)
{
    edge[e].u = v;
    edge[e].next = head[u];
    head[u] = e++;
    
    edge[e].u = u;
    edge[e].next = head[v];
    head[v] = e++;
}

void dfs(int u)
{
    visited[u] = true;
    dp[u][0] = 0, dp[u][1] = points[u].c;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].u;
        if(!visited[v])
        {
            dfs(v);
            dp[u][0] = max(dp[u][0], max(dp[v][0], dp[v][1]));
            if(dp[v][1] > 0)
                dp[u][1] += dp[v][1];
        }
    }
}