1、http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4772
2、题目大意：
有n个城镇，他们之间有路相通，知道每条路需要走的天数，每个城镇的价值，现在一个人想要从k点出发，在m天内去访问别的城镇，但是必须在m天之前返回k点，求可以获得的最大价值
dp[i][j]表示从i点出发走j天获得的最大价值，需要往返，注意m/=2即可
状态转移方程
dp[u][j]=max(dp[u][j],dp[u][j-k-w[u][v]]+dp[v][k]);
3、AC代码：
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 105
int val[N];
vector<int> adj[N*2];
int w[N][N];
int dp[N][N],vis[N],m;
void dfs(int u)
{vis[u]=1;dp[u][0]=val[u];for(int i=0;i<adj[u].size();i++){int v=adj[u][i];if(vis[v]==0){dfs(v);for(int j=m;j>=0;j--){for(int k=0;k<=j-w[u][v];k++){dp[u][j]=max(dp[u][j],dp[u][j-k-w[u][v]]+dp[v][k]);}}}}
}
int main()
{int n,a,b,c,k;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++)adj[i].clear();memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){scanf("%d",&val[i]);dp[i][0]=val[i];}for(int i=1;i<n;i++){scanf("%d%d%d",&a,&b,&c);adj[a].push_back(b);adj[b].push_back(a);w[a][b]=w[b][a]=c;}scanf("%d%d",&k,&m);m/=2;memset(vis,0,sizeof(vis));dfs(k);int ans=-1;for(int i=0;i<=m;i++){if(dp[k][i]>ans)ans=dp[k][i];}printf("%d\n",ans);}return 0;
}