poj 1155 TELE

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

树dp 背包

题意：有n个点的无根树，有m个用户，其中1号为电台，2到n-m为中转站，n-m+1到n是用户，另外用户一定是树的叶子。树的每条边有权，信号从1出发传播出去每走过一条边电台都会耗费金钱。一个用户，如果向他发送信号，那么他会对应地付钱，但是如果你不向他发送信号，他是不给钱的。最后就是，在保证电台不亏本的条件下，尽量向多的用户发送信号，问最多的用户数

这其实就是个权衡的问题，从1到每个叶子（用户）需要的花费cost可以知道，而每个叶子的价值val知道，选这个叶子的话，电台的收益其实是val-cost。要电台不亏钱，就是最终收益>=0。这种问题，一看就是背包嘛。一个叶子选或不选，选了要付出代价也有价值，不选的话就没代价也没价值，令到最后价值最大

我们现在定义：dp[u][m]，表示以u为根的子树选m个叶子的最大收益

这里需要想通一个问题，收益大，不代表选的叶子就多。但是！对于选m个叶子而言，令到收益最大，那肯定是没错的。例如，选了4个叶子最大收益是3，选了3个叶子最大收益是10，虽然10收益是大但是不代表叶子数多，我们的目标是叶子数最大而不是收益最大。但是，在选4个叶子，最大收益为3的时候，一定是最好的情况，在这种情况下，我们再考虑是否选5个，6个，7个叶子，一定是最优的（本问题的最优子结构）。

所以我们最后的答案是：dp[1][m]，以1为根的子树选m个孩子的最大收益，答案是m。假设1下面有cnt个叶子，我们从cnt向1枚举，找到第1个dp[1][m] >= 0，那么就可以结束，m就是答案

转移：

dp[u][0] = 0; //不选，无代价无价值，自然无收益

dp[u][1] = val[u]; //u是叶子，只能选1个叶子，收益就是u的价值，不用代价

dp[u][j] = max(dp[v][k] + dp[u][j-k] - w); //v是u儿子，w是u–>v的边权

这题数据给出来比较特殊，可以直接建树为有根数，不同建两条边

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
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
using namespace std;
#define N 3010
#define INF 0x3f3f3f3f
#define pii pair<int,int>
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair

int n,nleaf;
vector<pii>e[N];
int cnt[N],val[N];
int dp[N][N];

void dfs(int u,int fa,int dis){
	cnt[u] = 0;
	bool leaf = true;
	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i].first;
		int w = e[u][i].second;
		leaf = false;
		dfs(v,u,dis+w);
		cnt[u] += cnt[v];
	}
	if(leaf){
		cnt[u] = 1;
		dp[u][1] = val[u]; 
		return;
	}
	dp[u][0] = 0;
	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i].first;
		int w = e[u][i].second;
		for(int j = cnt[u]; j >= 1; j--)
			for(int k = 1; k <= j && k <= cnt[v]; k++)
				if(dp[u][j-k] != -INF && dp[v][k] != -INF){
					dp[u][j] = max(dp[u][j] , dp[u][j-k] + dp[v][k] - w);
				}
	} 
}

int main(){
	while(scanf("%d%d",&n,&nleaf)!=EOF){
		for(int i = 1; i <= n; i++)
			e[i].clear();
		for(int u = 1; u <= n-nleaf; u++){
			int m,v,w;
			scanf("%d",&m);
			while(m--){
				scanf("%d%d",&v,&w);
				e[u].pb(mp(v,w));
			}
		}
		for(int u = n-nleaf+1; u <= n; u++)
			scanf("%d",&val[u]);
		for(int i = 0; i <= n; i++)
			for(int j = 0; j <= n; j++)
				dp[i][j] = -INF;
		dfs(1,-1,0);
		int res = cnt[1];
		while(res){
			if(dp[1][res] >= 0) break;
			res--;
		}
		printf("%d\n",res);
	}
	return 0;
}