uva 1407 - Caves(树形dp)

题目链接：uva 1407 - Caves

题目大意：给出n，表示有一个以0为根含有n个节点的树，每条边有一个权值，现在给出m次询问，每次询问有一个val值，要求计算在val值下的距离最多能经过多少个节点，一个节点多次移动多算一次。

解题思路：dp[u][i]表示说以u为根，经过i个节点的最短距离，第三维有0和1两种状态，0是经过i个节点后要不用返回u，1是需要返回。这样就有(当考虑一个孩子节点v时）：

dp[u][j][0] = min(dp[u][j][0], dp[u][j-x][1]+dp[v][x][0]+val);  

dp[u][j][0] = min(dp[u][j][0], dp[u][j-x][0]+dp[v][x][1]+2*val);

dp[u][j][1] = min(dp[u][j][1], dp[u][j-x][1]+dp[v][x][1]+2*val);

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;
struct state {
	int v, val;
	state() { };
	state(int vi, int value) {
		this->v = vi;
		this->val = value;
	}
};

int n, m, vis[N], cnt[N], dp[N][N][2];
vector<state> g[N];

void init () {
	memset(vis, 0, sizeof(vis));
	memset(dp, INF, sizeof(dp));
	for (int i = 0; i < n; i++) g[i].clear();

	int a, b, value;
	for (int i = 1; i < n; i++) {
		scanf("%d%d%d", &a, &b, &value);
		g[a].push_back(state(b, value));
		g[b].push_back(state(a, value));
	}
}

void solve (int u) {
	vis[u] = cnt[u] = 1;
	dp[u][1][0] = dp[u][1][1] = 0;

	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].v, val = g[u][i].val;
		if (vis[v]) continue;
		solve(v);

		cnt[u] += cnt[v];
		for (int j = cnt[u]; j > 1; j--) {

			for (int x = 0; x <= j && x <= cnt[v]; x++) {
				dp[u][j][0] = min(dp[u][j][0], dp[u][j-x][1]+dp[v][x][0]+val);
				dp[u][j][0] = min(dp[u][j][0], dp[u][j-x][0]+dp[v][x][1]+2*val);
				dp[u][j][1] = min(dp[u][j][1], dp[u][j-x][1]+dp[v][x][1]+2*val);
			}
		}
	}	
}

int main () {
	int cas = 1;
	while (scanf("%d", &n) == 1 && n) {
		init();
		solve(0);

		printf("Case %d:\n", cas++);
		int a;
		scanf("%d", &m);
		while (m--) {
			scanf("%d", &a);
			for (int i = n; i; i--) if (dp[0][i][0] <= a) {
				printf("%d\n", i); break;
			}
		}
	}
	return 0;
}

uva 1407 - Caves(树形dp),布布扣,bubuko.com

uva 1407 - Caves(树形dp)

原文：http://blog.csdn.net/keshuai19940722/article/details/19933761