思路：先dfs一下，找出1，n间的路径长度和价值，回溯时将该路径长度和价值清零。那么对剩下的图就可以直接树形dp求解了。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #define inf 100000000 #define Maxn 110 using namespace std; int vi[Maxn],head[Maxn],dp[Maxn][510],e,n,T,a[Maxn],len,sum; struct Edge{ int u,v,next,val; }edge[Maxn*2]; void init() { memset(vi,0,sizeof(vi)); memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); e=len=sum=0; } void add(int u,int v,int val) { edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].next=head[u],head[u]=e++; edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].next=head[v],head[v]=e++; } int dfs(int u) { int i,v; vi[u]=1; if(u==1) { sum+=a[u]; a[u]=0; return 1; } for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(vi[v]) continue; if(dfs(v)) { len+=edge[i].val,edge[i].val=edge[i^1].val=0; sum+=a[u]; a[u]=0; return 1; } } return 0; } void Treedp(int u) { int i,v,j,k; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(vi[v]) continue; Treedp(v); int cost=2*edge[i].val; for(j=T;j>=cost;j--){ int temp=0; for(k=0;k<=j-cost;k++) temp=max(temp,dp[u][j-cost-k]+dp[v][k]); dp[u][j]=max(dp[u][j],temp); } } for(i=0;i<=T;i++) dp[u][i]+=a[u]; } int main() { int i,j,u,v,t; while(scanf("%d%d",&n,&T)!=EOF) { init(); for(i=1;i<n;i++){ scanf("%d%d%d",&u,&v,&t); add(u,v,t); } for(i=1;i<=n;i++) scanf("%d",a+i); dfs(n); if(len>T) { printf("Human beings die in pursuit of wealth, and birds die in pursuit of food! "); continue; } T-=len; memset(vi,0,sizeof(vi)); Treedp(n); printf("%d ",dp[n][T]+sum); } return 0; }