poj 1192 最优连通子集

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp

按点给出的顺序被点编号。“相邻”的点之间可以连一条边,最后得到的一棵树

题目是在树中找出一个连通的集合,使得点权最大(如果所有点都是负权,答案为0,即集合为空,不选任何点)

定1为根

设置状态:

dp[u][0]:在u所在子树中,不选点u的最优连通子集

dp[u][1]:在u所在子树中,选点u的最优连通子集

dp[u][0]:既然不能选u,那么连通子集必定来自于u下面的某个分支,而不可能跨越多个分支(否则必定经过u)

dp[u][0] = max( dp[v][0] , dp[v][1])

dp[u][1]:因为选了点u,可以连接不同的分支,但是要连一个分支的话,说明那个儿子必定要选,而且不是什么分支都连

只有大于0的才连,否则连上去要么不改变答案,要么令答案更小,肯定不是最优

dp[u][1] = sigma ( dp[v][1] ) dp[v][1] > 0

最后答案为 max(dp[1][0] , dp[1][1]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int u,v,next;
edge(){}
edge(int __u,int __v){
u = __u; v = __v;
}
}e[2*N];
int x[N],y[N],w[N],dp[N][2];

inline int abs(int m){
return m >= 0 ? m : -m;
}

inline bool check(int i,int j){
if(abs(x[i]-x[j]) + abs(y[i]-y[j]) == 1)
return true;
return false;
}

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

void dfs(int u,int fa){
dp[u][1] = w[u];
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(v == fa) continue;
dfs(v,u);
dp[u][0] = max(dp[v][0],dp[v][1]);
if(dp[v][1] > 0) dp[u][1] += dp[v][1];
}
}

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n; i++)
scanf("%d%d%d",&x[i],&y[i],&w[i]);
cl(head,-1); tot = 0;
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++)
if(check(i,j)){
add(i,j); add(j,i);
}
cl(dp,0);
dfs(1,-1);
printf("%d\n",max(dp[1][1],dp[1][0]));

}
return 0;
}