Hdu 1561(树形背包DP)

Hdu 1561
经典树形依赖背包问题。
因为可能出现森林,所有要建立一个虚结点0,将森林中所有树的根节点作为结点0的儿子
$f[i][j]$表示以i为根选j个课程
$f[u][j] = max(f[u][j], f[u][j-k]+f[v][k])$ v是u的儿子

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i,j) memset(i, j, sizeof(i));
using namespace std;
int n,m;
int c[205];
vector<int> G[205];
int f[205][205];
int t;
void dfs(int u)
{
for (int i=1;i<=m;i++)
f[u][i] = c[u];
for (int i=0;i<G[u].size();i++)
{
int v = G[u][i];
dfs(v);
for (int j=t;j>=2;j--)
for (int k=1;k<j;k++)
f[u][j] = max(f[u][j], f[u][j-k]+f[v][k]);
}
}
int main()
{
while (scanf("%d%d", &n, &m)==2&&(n||m))
{
for (int i=0;i<=n;i++) G[i].clear();
ms(f,0);
for (int i=1;i<=n;i++)
{
int ai;
scanf("%d%d", &ai, &c[i]);
G[ai].push_back(i);
}
t = m+1;
dfs(0);
printf("%d\n", f[0][m+1]);
}
return 0;
}

------ 本文结束 ------