和前一篇博客很相像 ;
d[ 0] [ root ][ k ]表示从root出发不需要回到root需要走k个节点的最小路径长度;
d[ 1] [ root ][ k ]表示从root出发必须要回到root需要走k个节点的最小路径长度;
再次说明一下本题目这样动态规划就从k =n 递减查找最优值d[ 0][ root ][ k ] <= x 的最大 k;
状态转移很清晰 such as : d[ 0 ][ root ][ k ] = min(d[0][root ][k] ,d[0][root ][k - j ] + d[ 1 ][ son ][ j ] +2*w(root -->son) ) ;
d[ 0 ][ root ][ k ] = min(d[0][root ][k] ,d[1][root ][k - j ] + d[ 0 ][ son ][ j ] +w(root -->son) ) ;
而对于1的转移只需一个式子;
#include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const LL inf = 1e11; const int maxn = 505; LL d[2][maxn][maxn]; struct node{ int to,val; node(int x=0,int y=0):to(x),val(y){} }; vector<node> G[maxn]; LL father[maxn],tem[2][maxn],n,son[maxn]; int dfs(int u){ son[u] = 1; for(int i=0;i<G[u].size();i++){ son[u]+=dfs(G[u][i].to); } return son[u]; } void solve(int root){ for(int i=0;i<=n;i++){ d[0][root][i] = d[1][root][i] = inf; } d[0][root][1] = 0; d[1][root][1] = 0; for(int i=0;i<G[root].size();i++){ int v = G[root][i].to; int w = G[root][i].val; solve(v); for(int i=0;i<=son[root];i++){ tem[0][i] = d[0][root][i]; tem[1][i] = d[1][root][i]; } for(int i=2;i<=son[root];i++) for(int j=1;j<i;j++){ d[0][root][i]=min(d[0][root][i],tem[1][i-j]+d[0][v][j]+w); d[0][root][i]=min(d[0][root][i],tem[0][i-j]+d[1][v][j]+2*w); d[1][root][i]=min(d[1][root][i],tem[1][i-j]+d[1][v][j]+2*w); } } } int main() { int kase=1; while(scanf("%d",&n)==1 && n){ for(int i=0;i<=n;i++) G[i].clear(); memset(father,0,sizeof(father)); for(int i=1;i<n;i++){ int x,y,val; scanf("%d %d %d",&x,&y,&val); father[x] = 1; G[y].push_back(node(x,val)); } int root; for(int i=0;i<n;i++){ if(!father[i]){ root=i; dfs(root); solve(root); break; } } printf("Case %d:\n",kase++); int Q; scanf("%d",&Q); while(Q--){ int x; scanf("%d",&x); int p = upper_bound(d[0][root],d[0][root]+n+1,x)-d[0][root]; printf("%d\n",p-1); } } return 0; }