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