程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU4276 The Ghost Blows Light 樹形DP

HDU4276 The Ghost Blows Light 樹形DP

編輯：C++入門知識

做這個題的時候想到了，先來一遍最短路，判斷是否可以到達，若可以減去最短路的花費，再在剩下的花費裡進行DP求最優解，想到了但是沒做到，很多細節沒有處理好，結果崩盤了，唉，看題解很多人都是兩邊dfs，不過這位大牛也是先spfa了一遍，給我這個弱菜看看剛好，這篇好好記錄下來，

最後參考了大牛的：http://blog.csdn.net/acm_cxlove/article/details/7964739，可以說是一模一樣了

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const LL INF = 1LL<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

typedef struct Node {
	int fro,to;
	int nex;
	int val;
};

Node edge[100 * 4];

int value[100 + 5];
int head[100 + 5];
bool vis[100 + 5];
int dis[100 + 5];
int father[100 + 5];
int mark[100 + 5];
int dp[100 + 5][500 + 5];

int tot;

int n,t;

void init() {
	memset(head,-1,sizeof(head));
	memset(value,0,sizeof(value));
	memset(edge,0,sizeof(edge));
	memset(mark,0,sizeof(mark));
	memset(dp,0,sizeof(dp));
	tot = 0;
}

void add(int u,int v,int w) {
	edge[tot].fro = u;
	edge[tot].to = v;
	edge[tot].val = w;
	edge[tot].nex = head[u];
	head[u] = tot++;
}

void spfa() {
	for(int i=0;i<=n;i++)
		dis[i] = inf;
	dis[1] = 0;
	memset(vis,false,sizeof(vis));
	memset(father,0,sizeof(father));
	queue q;
	int s = 1;
	q.push(s);
	vis[s] = true;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(int i = head[u];i != -1;i = edge[i].nex) {
			int v = edge[i].to;
			int val = edge[i].val;
			if(dis[v] > dis[u] + val) {
				dis[v] = dis[u] + val;
				father[v] = u;
				mark[v] = i;
				if(!vis[v]) {
					vis[v] = true;
					q.push(v);
				}
			}
		}
	}
	for(int i=n;i != 1;i=father[i])
		edge[mark[i]].val = 0;
}

void dfs(int u,int fa) {
	for(int i=head[u];i!=-1;i=edge[i].nex) {
		int v = edge[i].to;
		int val = edge[i].val * 2;
		if(v == fa)continue;
		dfs(v,u);
		for(int j=t;j>=val;j--)
			for(int k = j-val;k>=0;k--)
				dp[u][j] = max(dp[u][j],dp[u][k] + dp[v][j - k - val]);
	}
	for(int i=0;i<=t;i++)
		dp[u][i] += value[u];
}

int main() {
	while(scanf("%d %d",&n,&t) == 2) {
		init();
		for(int i = 1;i < n;i++) {
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
		}
		for(int i = 1;i <= n;i++)
			scanf("%d",&value[i]);
		spfa();
		if(dis[n] > t) {
			puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");
			continue;
		}
		t -= dis[n];
		dfs(1,0);
		printf("%d\n",dp[1][t]);
	}
	return 0;
}