HDU 4276 The Ghost Blows Light（12年长春市 树形DP+spfa）

HDU 4276 The Ghost Blows Light（12年长春 树形DP+spfa）

转载请注明出处，谢谢http://blog.****.net/acm_cxlove/article/details/7854526       by---cxlove 

题目：给出一棵树，从1走到n，总时间为T，每走一条边需要花费一定时间，每个结点有一定价值，问在指定时间内回到T的能获取的最大价值

http://acm.hdu.edu.cn/showproblem.php?pid=4276 

比赛的时候是yobobobo出的这题。

不知道怎么处理回到n点，果然DP不是我的菜。

首先spfa求一次最短路，如果从1到n的最短花费都小于总时间，则是不可能。

而且在最短路的时候记录每个节点的父节点，以及边的编号

然后将最短路径上的所有边权置为0.将总时间减去最短路径。

这样处理的目的是，显然最短路上的边只会走一遍才是最优的，而且剩下的边要么不走，要么走两次，而且DFS求一次树形DP之后，不需要考虑回到n的情况，因为1-n的最短路径走了一遍，其它边走0次或两次，肯定是回到n的。

这样就成了树上的分组背包了~~~囧，

树形DP很弱，手很生

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
#define inf 1<<27
#define N 105
#define M 505
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct Node{
	int v,w,next;
}edge[N*2];
int tot,start[N],val[N],dist[N];
int n,t,dp[N][M],pre[N],p[N];
void _addedge(int u,int v,int w){
	edge[tot].v=v;edge[tot].w=w;
	edge[tot].next=start[u];
	start[u]=tot++;
}
void addedge(int u,int v,int w){
	_addedge(u,v,w);
	_addedge(v,u,w);
}
void spfa(int s){
	queue<int>que;
	int vis[N];
	mem(vis,0);mem(pre,0);
	for(int i=1;i<=n;i++)
		if(i==s)
			dist[i]=0;
		else
			dist[i]=inf;
	que.push(s);
	vis[s]=1;
	while(!que.empty()){
		int u=que.front();
		que.pop();
		vis[u]=0;
		for(int i=start[u];i!=-1;i=edge[i].next){
			int v=edge[i].v,w=edge[i].w;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				pre[v]=u;
				p[v]=i;
				if(!vis[v]){
					vis[v]=1;
					que.push(v);
				}
			}
		}
	}
	for(int i=n;i!=1;i=pre[i]){
		edge[p[i]].w=0;
		edge[p[i]^1].w=0;
	}
}
void dfs(int u,int father){
	for(int i=start[u];i!=-1;i=edge[i].next){
		int v=edge[i].v,w=edge[i].w*2;
		if(v==father) continue;
		dfs(v,u);
		for(int i=t;i>=w;i--)
			for(int j=i-w;j>=0;j--)
				dp[u][i]=max(dp[u][i],dp[u][j]+dp[v][i-j-w]);
	}
	for(int i=0;i<=t;i++)
		dp[u][i]+=val[u];
}
int main(){	
	while(scanf("%d%d",&n,&t)!=EOF){
		tot=0;mem(start,-1);
		for(int i=1;i<n;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			addedge(u,v,w);
		}
		for(int i=1;i<=n;i++)
		    scanf("%d",&val[i]);
		spfa(1);
		if(dist[n]>t){
			puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
			continue;
		}
		mem(dp,0);
		t-=dist[n];
		dfs(1,0);
		printf("%d\n",dp[1][t]);
	}
	return 0;
}