首页 > ACM题库 > HDU-杭电 > HDU 3672-Caves[解题报告]HOJ
2014
11-30

HDU 3672-Caves[解题报告]HOJ

Caves

问题描述 :

It is said that the people of Menggol lived in caves. A tribe’s caves were connected to each other with paths. The paths were so designed that there was one and only one path to each cave. So the caves and the paths formed a tree. There was a main cave, which connected the world outside. The Menggolian always carved a map of the tribe’s caves on the wall of the main cave.

Scientists have just discovered Menggolian’s tribe. What a heart-stirring discovery! They are eager to explore it. Since the terrain is very complex and dangerous, they decide to send out a robot.

The robot will be landed into the main cave, where he will begin his adventure. It doesn’t have to return to the main cave, because the messages of his exploration will be sent immediately to the scientists while he is on the way.

A robot can only walk x meters before it runs out of energy. So the problem arises: given the map of the tribe’s caves and a set of x , how many caves can be explored at most?

输入:

There are multiple test cases in the input file. Each test case starts with a single number n (0<=n<=500) , which is the number of caves, followed by n – 1 lines describing the map. Each of the n – 1 lines contains three integers separated by blanks: i , j , and d (1<=d<=10000) . It means that the i -th cave’s parent cave is the j -th cave and the distance is d meters. A parent cave of cave i is the first cave to enter on the path from i to the main cave. Caves are numbered from 0 to n – 1 . Then there is an integer q (1<=q<=1000) , which is the number of queries, followed by q lines. For one query, there is one integer x (0<=x<=5000000) , the maximum distance that the robot can travel. n = 0 indicates the end of input file.

输出:

There are multiple test cases in the input file. Each test case starts with a single number n (0<=n<=500) , which is the number of caves, followed by n – 1 lines describing the map. Each of the n – 1 lines contains three integers separated by blanks: i , j , and d (1<=d<=10000) . It means that the i -th cave’s parent cave is the j -th cave and the distance is d meters. A parent cave of cave i is the first cave to enter on the path from i to the main cave. Caves are numbered from 0 to n – 1 . Then there is an integer q (1<=q<=1000) , which is the number of queries, followed by q lines. For one query, there is one integer x (0<=x<=5000000) , the maximum distance that the robot can travel. n = 0 indicates the end of input file.

样例输入:

3 
1 0 5 
2 0 3 
3 
3 
10 
11 
0

样例输出:

Case 1: 
2 
2 
3

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string.h>
using namespace std;

#define MAXN 600
#define INF 0x3f3f3f3f

struct Node{
	int v,e;
	Node *next;
}*edge[MAXN],space[MAXN<<1];

int f[MAXN][MAXN][2],C,son[MAXN];

void addedge(int x,int y,int z){
	Node *p=&space[C++];
	p->v=x; p->e=z; p->next=edge[y];
	edge[y]=p;
}

void dfs(int x,int fa){
	f[x][1][0]=0; f[x][1][1]=0;
	son[x]=1;
	for (Node *p=edge[x]; p; p=p->next){
		if (p->v!=fa){
			int y=p->v;
			dfs(y,x);
			son[x]+=son[y];
			for (int i=son[x];i>1;i--)
				for (int j=1;j<=son[y];j++){
					f[x][i][0]=min(f[x][i][0],f[x][i-j][0]+f[y][j][0]+(p->e)*2);
					f[x][i][1]=min(f[x][i][1],f[x][i-j][0]+f[y][j][1]+p->e);
					f[x][i][1]=min(f[x][i][1],f[x][i-j][1]+f[y][j][0]+(p->e)*2);
				}
		}
	}
}

int main(){
	int caseT=0,x,y,z,n,Q,t;
	while (scanf("%d",&n),n){
		C=0;
		for (int i=0;i<=n;i++) edge[i]=NULL;
		for (int i=1;i<n;i++){
			scanf("%d%d%d",&x,&y,&z);
			addedge(x+1,y+1,z); addedge(y+1,x+1,z);
		}
		memset(son,0,sizeof(son));
		for (int i=0;i<=n;i++)
			for (int j=0;j<=n;j++) f[i][j][0]=f[i][j][1]=INF;
		dfs(1,0);
		scanf("%d",&Q);
		printf("Case %d:\n",++caseT);
		for (int i=1;i<=Q;i++){
			scanf("%d",&t);
			int ans=1;
			for (int i=n;i>=1;i--){
				if (f[1][i][0]<=t||f[1][i][1]<=t){
					ans=i; break;
				}
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

  1. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  2. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  3. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  4. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  5. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  6. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  7. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  8. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  9. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  10. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  11. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  12. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  13. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  14. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  15. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  16. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  17. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  18. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  19. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  20. 【多看,多想,解决问题】收到!咱俩定位不同,我喜欢针对内容发评论说看法,有互动当然更好可以取长补短交流心得。网络有句话:内容因评论而精彩…我不潜水也不灌水,我灌的是情绪。

  21. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。