#include <stdio.h> #include <string.h> #include <stdlib.h> const int N = 210; int n,m; int head[N],son[N]; int w[N]; int dp[N][N]; int max(int a,int b) {return a > b ? a : b;} int dfs(int fa) { int i,j,k; int tot = 1; dp[fa][1] = w[fa]; for(i = son[fa]; i != -1; i = head[i]) { tot += dfs(i); //剪枝,每次只用循环到当前能达到的最大值。 for(j = tot; j >= 1; j--) for(k = 1; k+j <= tot+1; k++) dp[fa][j+k] = max(dp[fa][j+k],dp[fa][j]+dp[i][k]); } return tot; } int main() { int i,k; while(scanf("%d%d",&n,&m),n+m) { memset(son,-1,sizeof(son)); w[0] = 0; for(i = 1; i <= n; i++) { scanf("%d%d",&j,w+i); head[i] = son[j]; son[j] = i; } memset(dp,sizeof(dp)); dfs(0); printf("%d\n",dp[0][m+1]); } return 0; }
#include <stdio.h> #include <string.h> #define MAX 210 #define max(a,b) (a)>(b) ? (a) : (b) struct node { int v; node *next; }*head[MAX],tree[MAX]; int n,m,money[MAX]; int ptr,dp[MAX][MAX]; void Initial() { ptr = 1; memset(dp,sizeof(dp)); memset(head,NULL,sizeof(head)); } void AddEdge(int fa,int son) { tree[ptr].v = son; tree[ptr].next = head[fa]; head[fa] = &tree[ptr++]; } int Tree_DP(int v) { int i,k,tot = 1; node *p = head[v]; while (p != NULL) { tot += Tree_DP(p->v); int tp = tot < m ? tot : m; //加个剪枝,这个到目前为止能到达最大容量 for (j = tp; j >= 1; --j) //分组背包 for (i = 1; i <= j; ++i) dp[v][j] = max(dp[v][j],dp[p->v][i]+dp[v][j-i]); p = p->next; } if (v != 0) { for (j = m; j >= 1; --j) dp[v][j] = dp[v][j-1] + money[v]; //必选当前节点自己 } return tot; } int main() { int i,a,b; while (scanf("%d%d",n+m) { Initial(); for (i = 1; i <= n; ++i) { scanf("%d%d",&a,&b); money[i] = b; AddEdge(a,i); } Tree_DP(0); printf("%d\n",dp[0][m]); } }