链接：点击打开链接
题意：给一棵树，每条边有边权，有Q次询问，求从根节点出发，走不超过x单位距离，最多经过多少个点
代码：
#include <vector> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; const int INF=0x3f3f3f3f; struct node{ int to,cost; }; vector<node> G[505]; int ans[505],vis[505],sum[505],dp[505][505][2]; void dfs(int s){ int i,j,k,tmp; vis[s]=1; for(i=0;i<G[s].size();i++){ tmp=G[s][i].to; if(vis[tmp]) continue; dfs(tmp); sum[s]+=sum[tmp]; for(j=sum[s];j>1;j--){ for(k=min(sum[tmp],j-1);k>=0;k--){ dp[s][j][0]=min(dp[s][j][0],dp[s][j-k][0]+dp[tmp][k][0]+2*G[s][i].cost); dp[s][j][1]=min(dp[s][j][1],min(dp[s][j-k][1]+dp[tmp][k][0]+2*G[s][i].cost,dp[s][j-k][0]+dp[tmp][k][1]+G[s][i].cost)); } //转移的时候一定要想清楚 } } } //dp[i][j][0]表示走到i点，经过j个点后回到i点 int main(){ //dp[i][j][0]表示走到i点，经过j个点后不回到i点 int n,i,j,x,y,z,q,cas,tmp; cas=1; while(scanf("%d",&n)!=EOF&&n){ for(i=0;i<n;i++) G[i].clear(); for(i=1;i<n;i++){ scanf("%d%d%d",&x,&y,&z); G[y].push_back((node){x,z}); G[x].push_back((node){y,z}); } memset(dp,INF,sizeof(dp)); for(i=0;i<=n;i++){ vis[i]=0,sum[i]=1; dp[i][1][0]=dp[i][1][1]=0; } dfs(0); for(i=1;i<=n;i++) //ans[i]为走i个点最近的路程 ans[i]=min(dp[0][i][0],dp[0][i][1]); scanf("%d",&q); printf("Case %d:\n",cas++); while(q--){ scanf("%d",&x); tmp=1; for(i=1;i<=n;i++){ //也可以二分找 if(ans[i]<=x) tmp=i; else break; } printf("%d\n",tmp); } } return 0; }