G-rated

What are you waiting for?

0%

poj 2152 Fire

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

树dp

题意：给一个n个点的无根树，要选一些点做消防站，没有被选的点要被消防站覆盖，目的是所有点都被覆盖（或者它本事是消防站）。另外每个点有个权值，选了它会产生这么多花费。另外每个点有个限制值D，如果它本身不是消防站，那么在距离D内一定要有1个消防站。问覆盖所有点的最小花费

设置状态：

dp[u][i]:必选i这个点做消防站，并且u是被i覆盖的（或者i就是u，这样也算是一种“覆盖”），然后u的子树被完全覆盖的最小花费（显然这里有个条件就是dis[u][i] <= D[u]，即u和i的距离要在u的限制距离内，否则u无法被i覆盖）

best[u]:覆盖u的子树需要的最小花费

定1为根得到有根树的话，显然答案就是best[1]

考虑转移：

先考虑best[u]，显然是从dp[u][k]里面考虑，必然是选最小的，best[u] = min( dp[u][k] );

考虑dp[u][k]，因为是必选了k且u一定被k覆盖，那么u的儿子v呢？如果v是被k覆盖的，那么取dp[v][k],如果不是v就是被其他点覆盖的，那么最小的花费肯定是best[v]

dp[u][k] = sigma( min(dp[v][k]-cost[k],best[v]) ) + cost[k];

//主要dis[v][k] <= D[v],即k这个消防站要能作用到v上

//减去cost[k]是不能多次重复计算k这个消防站的花费，而选了k这个消防站，要加上它的花费cost[k]

因为一开始要先预处理出任意两点间的距离dis[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>
#include <utility>
#include <vector>
using namespace std;
#define N 1010
#define INF 100000000000LL
#define LL long long
#define pil pair<int,long long>
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back
#define mp make_pair

int n;
LL cost[N],d[N],dp[N][N],best[N],dis[N][N];
vector<pil>e[N];

void cal(int rt,int u,int fa,LL len){
	dis[rt][u] = len;
	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i].first;
		LL w = e[u][i].second;
		if(v == fa) continue;
		cal(rt,v,u,len+w);
	}
}

void dfs(int u,int fa){
	for(int i = 0; i < e[u].size(); i++){
		int v = e[u][i].first;
		if(v == fa) continue;
		dfs(v,u);
	}

	LL Min = INF;
	for(int k = 1; k <= n; k++){
		if(dis[u][k] <= d[u]){
			dp[u][k] = 0;
			for(int i = 0; i < e[u].size(); i++){
				int v = e[u][i].first;
				LL w = e[u][i].second;
				if(v == fa) continue;
				dp[u][k] += min(dp[v][k]-cost[k],best[v]);
			}
			dp[u][k] += cost[k];
		}
		else dp[u][k] = INF;
		Min = min(Min,dp[u][k]);
	}
	best[u] = Min;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i = 1; i <= n; i++)
			scanf("%lld",&cost[i]);
		for(int i = 1; i <= n; i++)
			scanf("%lld",&d[i]);
		for(int i = 1; i <= n; i++)
			e[i].clear();
		for(int i = 1; i < n; i++){
			int u,v; LL w;
			scanf("%d%d%lld",&u,&v,&w);
			e[u].pb(mp(v,w)); e[v].pb(mp(u,w));
		}
		for(int i = 1; i <= n; i++)
			cal(i,i,-1,0);
		for(int i = 1; i <= n; i++)
			best[i] = INF;
		dfs(1,-1);
		printf("%lld\n",best[1]);
	}
	return 0;
}