http://acm.hdu.edu.cn/showproblem.php?pid=1561
题意：有n个点，容量为m，每个点有一个价值，还给出n条边，代表选第i个点之前必须先选ai，问最多的价值能取多少。
思路：每个点的花费是1，价值为w[i]，然后直接按照树型背包写就行了。
还是老套路。
dp[i][j] 表示以 i 为根结点的子树最大价值，然后像01背包一样枚举容量，再用一层循环去给子结点分配容量，最后回溯到根节点，根节点的值就是答案了。
因为是森林，所以添加一个0结点当作根，记得0结点是没有花费也没有价值的。
感觉写的不是很严谨，直接认为是一棵树了，没考虑缩点。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 205 4 struct Edge { 5 int v, nxt; 6 } edge[N]; 7 int head[N], tot, w[N], c[N], n, m, dp[N][N], deg[N]; 8 9 void Add(int u, int v) { edge[tot] = (Edge) {v, head[u]}; head[u] = tot++; } 10 11 void dfs(int u) { 12 for(int j = m; j >= c[u]; j--) dp[u][j] = w[u]; // 赋予初值,因为必须选第u个点,才能去更新子结点 13 for(int i = head[u]; ~i; i = edge[i].nxt) { 14 int v = edge[i].v; 15 dfs(v); 16 for(int j = m; j >= c[u]; j--) { 17 for(int k = 0; k <= j - c[u]; k++) { // 枚举分配给子结点的容量 18 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]); 19 } 20 } 21 } 22 } 23 24 void solve() { 25 for(int i = 1; i <= n; i++) c[i] = 1; 26 memset(dp, 0, sizeof(dp)); 27 memset(deg, 0, sizeof(deg)); 28 memset(head, -1, sizeof(head)); 29 tot = 0; 30 for(int i = 1; i <= n; i++) { 31 int a; scanf("%d%d", &a, &w[i]); 32 if(a == 0) continue; 33 Add(a, i); deg[i]++; 34 } 35 for(int i = 1; i <= n; i++) if(!deg[i]) Add(0, i); 36 dfs(0); 37 printf("%d ", dp[0][m]); 38 } 39 40 int main() { 41 while(scanf("%d%d", &n, &m), n + m) solve(); 42 return 0; 43 }