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;
}