hdu 4003 Find Metal Mineral

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

树dp + 背包思想

如果能想明白一个最优性的问题,就能理解为什么跟背包联系在一起

对于以u为根(包括u)的子树,如果派了k个机器人下去,注意这里k >= 2

那么没有一个机器人会再从u这里跑出来!

如果是派了1个机器人下去,那么有可能不再出来了,也可能会重新出来

为什么在k>=2的时候不会再跑出来了?

假设k个进去,有一个出来,称出来的机器人为x,那么x至少走了一条路径进去,然后又走出来

(即至少一条路径被重复走了),那么这条重复的路径,完全可以由其他的机器人代劳,不必要x去走重复的

也就是说,与其派k个下去,让其他一个走了重复路径,不如派k-1个下去,能做到同样的效果

而多出来的那个,从fa到u要花费,从u离开到fa也要花费,显然不是最优

所以定义的dp状态为,dp[u][k],派k个机器人下去u的子树(并且这k个机器人不会再离开u)的最小花费

那么目标状态就是dp[S][K]

dp[u][k] = min(dp[u][k-kk] + dp[v][kk] + kk * w);

特别的,dp[u][0],表示的其实是派了1个机器人下去u的子树走遍了整个子树再回到u

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 10010
#define M 15
#define MAX 20100
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,S,K,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[MAX];
int dp[N][M];

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){
for(int i = head[u]; i != -1; i = e[i].next){
int v = e[i].v;
int w = e[i].w;
if(v == fa) continue;
dfs(v,u);
for(int k = K; k >= 1; k--){
int res1 = dp[u][k-1] + dp[v][1] + w;
int res2 = dp[u][k] + dp[v][0] + 2 * w;
dp[u][k] = min(res1,res2);
for(int kk = 1; kk <= k ;kk++){
dp[u][k] = min(dp[u][k],dp[u][k-kk] + dp[v][kk] + kk * w);
}
}
dp[u][0] += dp[v][0] + 2 * w;
}
}

int main(){
while(scanf("%d%d%d",&n,&S,&K)!=EOF){
cl(head,-1); tot = 0;
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);
}
cl(dp,0);
dfs(S,-1);
printf("%d\n",dp[S][K]);
}
return 0;
}