首页 > ACM题库 > HDU-杭电 > HDU 4276-The Ghost Blows Light-动态规划-[解题报告]HOJ
2015
05-23

HDU 4276-The Ghost Blows Light-动态规划-[解题报告]HOJ

The Ghost Blows Light

问题描述 :


My name is Hu Bayi, robing an ancient tomb in Tibet. The tomb consists of N rooms (numbered from 1 to N) which are connected by some roads (pass each road should cost some time). There is exactly one route between any two rooms, and each room contains some treasures. Now I am located at the 1st room and the exit is located at the Nth room.
Suddenly, alert occurred! The tomb will topple down in T minutes, and I should reach exit room in T minutes. Human beings die in pursuit of wealth, and birds die in pursuit of food! Although it is life-threatening time, I also want to get treasure out as much as possible. Now I wonder the maximum number of treasures I can take out in T minutes.

输入:

There are multiple test cases.
The first line contains two integer N and T. (1 <= n <= 100, 0 <= T <= 500)
Each of the next N – 1 lines contains three integers a, b, and t indicating there is a road between a and b which costs t minutes. (1<=a<=n, 1<=b<=n, a!=b, 0 <= t <= 100)
The last line contains N integers, which Ai indicating the number of treasure in the ith room. (0 <= Ai <= 100)

输出:

There are multiple test cases.
The first line contains two integer N and T. (1 <= n <= 100, 0 <= T <= 500)
Each of the next N – 1 lines contains three integers a, b, and t indicating there is a road between a and b which costs t minutes. (1<=a<=n, 1<=b<=n, a!=b, 0 <= t <= 100)
The last line contains N integers, which Ai indicating the number of treasure in the ith room. (0 <= Ai <= 100)

样例输入:

5 10
1 2 2 
2 3 2
2 5 3
3 4 3
1 2 3 4 5

样例输出:

11

转载请注明出处,谢谢http://blog.csdn.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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7964739