dp[i][j]表示 用i 个士兵 在j为根节点的 最大值
#include<stdio.h> #include<iostream> #include<string.h> #include<queue> #include<algorithm> using namespace std; struct node{ int a,b; }p[110]; vector<int> q[110]; //用vector存 邻接表 int dp[110][110],f[110],m; void dfs(int s,int k) { int i,j,t; f[k]=1; for(i=p[k].a;i<=m;i++) //赋初值,比较神奇。。 dp[i][k]=p[k].b; int len=q[k].size(); for(i=0;i<len;i++) //一个分组背包 { if(f[q[k][i]]==1) continue; if(s > p[k].a) dfs(s-p[k].a,q[k][i]); for(j=s;j-p[k].a>=0;j--)// 这里注意要 j-p[k].a for(t=1;t<=j-p[k].a;t++) dp[j][k]=max(dp[j][k],dp[j-t][k]+dp[t][q[k][i]]); } } int main() { int n,i,k; while(scanf("%d%d",&n,&m),n!=-1||m!=-1){ int t1,t2; memset(dp,sizeof(dp)); memset(f,sizeof(f)); for(i=1;i<=n;i++){ q[i].clear(); scanf("%d%d",&t1,&t2); p[i].a=(t1%20==0)?(t1/20):(t1/20+1);//... p[i].b=t2; } for(i=1;i<n;i++) { scanf("%d%d",&t2); q[t1].push_back(t2); q[t2].push_back(t1); } if(m==0) //这条件不加,就错了! printf("0\n"); else { dfs(m,1); printf("%d\n",dp[m][1]); } } }