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;
}