HDU4276 The Ghost Blows Light SPFA & 트리 dp

제목의 소개와 사고방식은 아래의 블로그를 완전히 참고하였다.http://blog.csdn.net/acm_cxlove/article/details/7964739
이 문제를 푸는 것은 주로 SPFA 코드에 대한 자신의 훈련과 트리 dp에 대한 사고방식의 단련을 강화하기 위해서이다.나는 특별히 나무 dp의 부분을 연구했다

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]);

			}

		}

순환 안에서는 순서를 틀릴 수 없다. 바깥쪽의 i 역순은 분명하지만 왜 안쪽에 문제가 있을까?w는 되니까=0, 이럴 때 상상해봐, j=i-w면
dp[u][i]=max(dp[u][i], dp[u][i]+dp[v][i-j-w]), 그러나 dp[u][i]는 이미 업데이트되었기 때문에 오류가 발생할 수 있습니다. 두 층의 순환은 반드시 역순으로 해야 합니다.
아래에 코드를 한 통 붙이다

#pragma warning(disable:4996)

#include<iostream>

#include<cstring>

#include<string>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<vector>

#include<queue>

#define maxn 150

using namespace std;



struct Edge

{

	int u, v, w;

	Edge(){}

	Edge(int ui, int vi, int wi) :u(ui), v(vi), w(wi){}

}e[2*maxn];



int n, t;

int val[maxn];

int ecnt;



int first[maxn], nxt[2 * maxn];



void add(int u, int v, int w)

{

	e[ecnt].u = u; e[ecnt].v = v; e[ecnt].w = w;

	nxt[ecnt] = first[u];

	first[u] = ecnt++;

}



int dis[maxn], vis[maxn];

int p[maxn];



void spfa(int s)

{

	memset(dis, 0x3f, sizeof(dis));

	memset(vis, 0, sizeof(vis));

	memset(p, -1, sizeof(p));

	queue<int> que;

	que.push(s); vis[s] = 1;

	dis[s] = 0;

	while (!que.empty())

	{

		int u = que.front(); que.pop();

		vis[s] = 0;

		for (int i = first[u]; i != -1; i = nxt[i]){

			int v = e[i].v;

			if (dis[v] > dis[u] + e[i].w){

				dis[v] = dis[u] + e[i].w;

				p[v] = i;

				if (!vis[v]){

					que.push(v);

					vis[v] = 1;

				}

			}

		}

	}

}



int dp[maxn][550];



void dfs(int u, int fa)

{

	for (int i = first[u]; i != -1; i = nxt[i]){

		int v = e[i].v, w = e[i].w * 2;

		if (v == fa) 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 (cin >> n >> t)

	{

		int ui, vi, wi;

		memset(first, -1, sizeof(first));

		ecnt = 0;

		for (int i = 0; i < n - 1; i++){

			scanf("%d%d%d", &ui, &vi, &wi);

			add(ui, vi, wi);

			add(vi, ui, wi);

		}

		for (int i = 1; i <= n; i++) scanf("%d", val + i);

		spfa(1);

		if (dis[n]>t) {

			puts("Human beings die in pursuit of wealth, and birds die in pursuit of food!");

			continue;

		}

		for (int i = n; i != 1; i = e[p[i]].u){

			e[p[i]].w = e[p[i] ^ 1].w = 0;

		}

		t -= dis[n];

		memset(dp, 0, sizeof(dp));

		dfs(1, -1);

		printf("%d
", dp[1][t]);

	}

	return 0;

}