hdu 4267 The Ghost Blows Light

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4276)
参考链接：http://blog.csdn.net/u012841845/article/details/18739425
以及：http://blog.csdn.net/xianxingwuguan1/article/details/18954537
手写邻接表：http://blog.csdn.net/ooooooooe/article/details/17035501

分析：先寻找1到N的最短路径和走这段路所用的时间，再把路径的权置为0,如果时间有多的，就把剩余的时间拿来进行树上背包，具体过程我已经写在了程序的注释里，之所以要写这个，是因为网上关于这道题的文章虽然很多，但都讲解得不是很清楚。 head数组是一种手写邻接表的方法，在上面的网址可以找到，但是该博并没有说明，所以我特地去请教了另外的人。它是图的另一种存储方法，head[a]表示以a为起点的边的编号，下面的add函数中的head[u] = tol++是在更新编号(即改为当前边的编号)，表面上看起来它是在一直变化，但是每一次add它都会把自己的指存储在的edge结构体中，这样就可以根据一个head值一直找到它的父亲的父亲的父亲…另外，之所以说最短路上的边指走一遍是因为财宝只有那么多，拿了一次就没有了。

include <cstdio>
include <cstring>
include <iostream>
using namespace std;

const int maxn = 200;  
int head[maxn], tol, dpmaxn, weight[maxn], T, t, n;

// 此结构体表示各条边(这里其实是把room当做是有向无环图来看待，  
// 每一条边都以两个方向来表示，该结构体的元素含义如下：  
// next：表示下一条以当前边为起点的边(和邻接表的实现有些类似) 
// to：表示这条边的终点  
// time：表示走这条边所需要的时间  
// 另外两个就是默认构造函数和构造函数了  
struct node  
{  
	int next, to, time;  
  	node(){};  
	node(int next, int _to, int _time) : next(next), to(to), time(time){}  
}edge[5*maxn];

// add函数用来添加边(每条边用edge结构体表示)  
void add(int u, int v, int time)  
{  
	edge[tol] = node(head[u], v, time);  
	head[u] = tol++;  
}

// 深度搜索找到1到N的最短路径(即花费时间最少)  
// 并把该路径上的所有边所要的时间置为0，方便之后搜索，并得到最短时间为t  
// 其中u表示当前节点，pre表示上一个节点  
bool dfs(int u, int pre)  
{  
	if(u == n)  
      	return 1;  

	for(int i = head[u]; i != -1; i = edge[i].next)  
	{  
		int v = edge[i].to;  
		if( v == pre )  
			continue;  

		if(dfs(v, u)) // 当返回1时就表示采取了那一条边  
		{  
			t += edge[i].time;  
			edge[i].time = 0;  
			return 1;  
		}  
	}  
	return 0;
}

// 深度搜索，统计了所有节点在一定时间范围内所有时间所能获得的最大价值  
// dpu：表示从u点出发到回到u点，花费时间j所能获得的最大的财富  
void dfs1(int u, int pre)  
{  
	for(int i = 0; i <= T; i++) // T为剩下的总时间  
		dpu = weight[u]; // 只要是经过了这个节点的都应该把它的财宝即weight加起来  

	for(int i = head[u]; i != -1; i = edge[i].next) // 这就是上面使用邻接表的作用，方便深度搜索  
	{  
		int v = edge[i].to;  
		if( v == pre ) // 如果是指向上一条边的就直接略过  
			continue;  
		dfs1(v, u); // 递归   	
		int pp = 2*edge[i].time; // 与u点直接相连的那一条边的时间，因为如果要继续下去，就必然会经过该边  
		for(int j = T; j >= pp; j–) // j必须大于走那条边的时间，它表示的是从该边走的总时间  
			for(int k = 0; k <= j-pp; k++) // k表示走了那条边后从那条边的终点继续走所用的时间  
				dpu = max(dpu, dpv+dpu); // j-pp-k表示剩下的从u点出发走的时间  
	}  
}

int main()  
{  
	int i, j, k, p;  
	while(~scanf(“\%d\%d”, &n, &T))  
	{  
		memset(head, -1, sizeof(head));  
		tol = 0;  
		for(i = 1; i < n; i++)  
		{  
			scanf(“\%d\%d\%d”, &j, &k, &p);  
			add(j, k, p);  
			add(k, j, p);  
		}  
		for(i = 1; i <= n; i++)  
			scanf(“\%d”, &weight[i]);  
		t = 0;  
		dfs(1, 1);  
		if(t > T)  
		{  
			puts(“Human beings die in pursuit of wealth, and birds die in pursuit of food!”);  
			continue;  
		}  
		memset(dp, 0, sizeof(dp));  
		T -= t;  
		dfs1(1, -1);  
		cout<< dp1 <<endl; // 应该无论是否从1出发都能得到同样的结果的  
	}  
	return 0;  
}

这道题花了两天时间，写了七八张纸都没有完全理解清楚，难道真的是我太愚笨了吗？

评论 · Comments