poj 3345 Bribing FIPA

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

树dp 背包

题意:给一个n个点的有根森林(注意已经定了根的,不过是森林,即多棵树),每个点有权值。如果选了一个点,这个下面的子树的点都会被选上,得到的点数是整个子树的点数,而且花费只计算这个点的权值,现在给了一个m,即要选上m个点,并且令花费最少

这题,首先要搞好输入,因为输入有点恶心,学习了Yuan神的博客学了一些字符串的处理。

输入处理完构建了有根森林后,设置一个虚节点0,把所有树的根连起来,得到一个树,注意0的权值为0。
剩下来就是个背包问题

首先,一个点选了,就不能在它子树下再选了,因为选了这个点已经覆盖了整个子树的点,再选另一个点,这个花费肯定是多余的(另外题意好像也规定了不能这样选,读得不是太清楚,不过就算不说也可以想到的)

dp[u][m],表示u为根的子树下,选了m个节点的最小花费。

边界的设置:

dp[u][0] = 0; //一个子树下一个节点都不选,那么花费自然是0

dp[u][tot[u]] = val[u]; //tot[u]为u子树的总点数(包括u自己),因为整个子树都要选,那么唯一的方法其实就是选u自己,然后覆盖了整个子树,花费当然是val[u]

转移:

dp[u][j] = min(dp[u][j-k] + dp[v][k]); //v是u的儿子(不是孙子后代),另外注意k <= tot[v]

dp[u][j] = min(dp[u][j-k] + val[v]); //k = tot[v];因为对于v这个子树如果选了tot[v]个节点,其实就是选了v这个节点,覆盖了整个v子树,花费是val[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
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define N 210
#define INF 10000000
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,m,val[N],inde[N],tot[N],dp[N][N];
map<string,int>Map;
vector<int>e[N];

void dfs(int u){
tot[u] = 1;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
dfs(v);
tot[u] += tot[v];
}
dp[u][0] = 0; dp[u][tot[u]] = val[u];
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
for(int j = tot[u]-1; j >= 1; j--)
for(int k = 1; k <= j && k <= tot[v]; k++)
if(dp[u][j-k] != INF && dp[v][k] != INF){
if(k < tot[v])
dp[u][j] = min(dp[u][j] , dp[u][j-k] + dp[v][k]);
else
dp[u][j] = min(dp[u][j] , dp[u][j-k] + val[v]);
}
}
}

void solve(){
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
dp[i][j] = INF;
dfs(0);
int ans = INF;
for(int i = m; i <= n; i++)
if(dp[0][i] < ans) ans = dp[0][i];
printf("%d\n",ans);
}

int main(){
char str[10010];
while(gets(str)){
if(str[0] == '#') break;
sscanf(str,"%d%d",&n,&m);
cl(inde,0); cl(val,0); Map.clear();
for(int i = 0; i <= n; i++)
e[i].clear();
int id = 0,u,v;
for(int i = 0; i < n; i++){
scanf("%s",str);
if(Map.find(str) == Map.end())
Map[str] = ++id;
u = Map[str];
scanf("%d",&val[u]);
gets(str);
stringstream ss(str);
string node;
while(ss >> node){
if(Map.find(node) == Map.end())
Map[node] = ++id;
v = Map[node];
e[u].pb(v); inde[v]++;
}
}
for(int i = 1; i <= id; i++)
if(inde[i] == 0){
e[0].pb(i);
}
solve();
}
return 0;
}