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