uva 1407 Caves

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp 背包

题意:给一个无根树,机器人从0点出发,机器人能走的距离是D,问机器人最多能走几个点(一个点只被计算一次,但是从一条走过再走回来要计算2次花费)

转化为背包

dp[u][m][0],在u这个子树下走过了m个点并且回到u的最小花费

dp[u][m][1],z在u这个子树下走了m个点不回到u的最小花费

用了滚动数组,压缩了一维空间

转移:

dp[u][j][0] = min(dp[u][j][0] , dp[u][j-k][0] + dp[v][k][0]+2 * w);

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

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

w是u到v的边权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 510
#define INF 10000000
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int u,v,w,next;
edge(){}
edge(int __u,int __v,int __w){
u = __u; v = __v; w = __w;
}
}e[2*N];
int dp[N][N][2],cnt[N];

inline void add(int u,int v,int w){
e[tot] = edge(u,v,w);
e[tot].next = head[u]; head[u] = tot++;
}

void dfs(int u ,int fa){
cnt[u] = 1;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
int w = e[k].w;
if(v == fa) continue;
dfs(v,u);
cnt[u] += cnt[v];
}
dp[u][0][0] = dp[u][0][1] = 0;
dp[u][1][0] = dp[u][1][1] = 0;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
int w = e[k].w;
if(v == fa) continue;
for(int j = cnt[u]; j >= 2; j--)
for(int k = 0; k <= cnt[v] && k < j; k++){
dp[u][j][0] = min(dp[u][j][0] , dp[u][j-k][0] + dp[v][k][0]+2*w);
dp[u][j][1] = min(dp[u][j][1] , dp[u][j-k][0] + dp[v][k][1]+w);
dp[u][j][1] = min(dp[u][j][1] , dp[u][j-k][1] + dp[v][k][0]+2*w);
}
}
}

int main(){
int cas = 0;
while(scanf("%d",&n)!=EOF && n){
tot = 0; cl(head,-1);
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 = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
dp[i][j][0] = dp[i][j][1] = INF;
dfs(0,-1);
//for(int i = 0; i <= n; i++)
// printf("%d : %d %d\n",i,dp[0][i][0] ,dp[0][i][1]);
printf("Case %d:\n",++cas);
int q;
scanf("%d",&q);
while(q--){
int x;
scanf("%d",&x);
int res = n;
for(int i = 1; i <= n; i++)
if(dp[0][i][1] > x){
res = i-1; break;
}
printf("%d\n",res);
}
}
return 0;
}