灰色的果实

问题描述
树为灰色果实之树，不定时会长出灰色果实。贸然接近果实只会使得自己受其迷惑最后神经错乱而
浑浑噩噩不得终日，与死人无异。你的目标是成功到达树的顶端，砍下灰色果实的灵脉。
为了能够免除灰色果实的影响，你需要在灰色果实力量微弱时在树的各个点
设置若干个保护点，保护点内燃烧着镇定人心的香，以此来抵御灰色果实的精神
袭击。一个点必须在 lim[i]距离以内有保护点才能收到保护。而且，由于在树上
作业，地形十分崎岖，使得不同点设置保护点的作业时间 time[i]不同。
谋求最大的效率，请求出保护点笼罩整棵树所需的最短作业时间。
输入格式
第一行一个整数 n 表示树的初始节点数。
第二行 n 个整数 time[i] ，表示此点设置保护点的作业时间。
第三行 n 个整数 lim[i] ，表示点受到保护的限制距离。
第四行到第 n+3 行为树的初始边，有三个整数 x，y，z，代表 x 到 y 有一
条长度为 z 的枝条。
输出格式
一个数为保护点笼罩整棵树所需的最短作业时间。
样例输入（input.txt）
Sample1 Sample2
5
1 1 1 1 1
1 1 1 1 1
1 2 1
2 3 1
3 4 1
4 5 1
4
2 1 1 1
3 4 3 2
1 2 3
1 3 3
1 4 2
样例输出（output.txt）
Sample1 Sample2
2 2
数据范围
数据点 限制 其它限制
1
n≤20
边权≤150
保护所修建费用≤1000
这些都不重要
2
3
4
5
6
7
n≤100
8
9
10
11
n≤2000
12
13
14
15
16
17
18
19
20
注：[题意] 若有不懂的，可以理解为在 n 个点中设置若干个特殊点，使得特殊点保护
整棵树。
[答案] 答案保证在 int 范围之内。

30分暴力

$$Tips:一个点必须在 lim[i]距离以内有保护点才能受到保护，并不是保护点可以保护距离lim[i]的点$$

#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;
int n,num,ans,HA,ha;
int dis[2005][2005];
bool flag[2005],f[2005];
int tim[2005],lim[2005];
void dfs(int x,int zhi){if (zhi>=ans) return;if (zhi>1000) return;if (x>n){for (int i=1;i<=n;++i) flag[i]=true;int t=0;for (int i=1;i<=n;++i)if (f[i]==1){if (flag[i]){flag[i]=false;++t;}for (int j=1;j<=n;++j)if (flag[j]&&dis[i][j]<=lim[j]){flag[j]=false;++t;}}if (t==n) ans=min(ans,zhi);++HA;return;}f[x]=1;dfs(x+1,zhi+tim[x]);f[x]=0;dfs(x+1,zhi);
}
int main(){scanf("%d",&n);num=0;for (int i=1;i<=n;++i) scanf("%d",&tim[i]);for (int i=1;i<=n;++i) scanf("%d",&lim[i]);for (int i=1;i<=n;++i) f[i]=0;for (int i=1;i<=n;++i)for (int j=1;j<=n;++j) dis[i][j]=1<<29;for (int i=1;i<n;++i){int u,v,z;scanf("%d%d%d",&u,&v,&z);dis[u][v]=z;dis[v][u]=z;}for (int k=1;k<=n;++k)for (int i=1;i<=n;++i)if (i!=k) for (int j=1;j<=n;++j)if (k!=j&&i!=j)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);ans=1<<29;dfs(1,0);printf("%d\n",ans);return 0;
}

正解

$$树形DP，dp[i][j]表示第i号点被j号点保护的最小费用。$$
$$bst[i]为第 i 个点及其子树全部被保护所需最小代价$$

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int vet[4010],val[4010],Next[4010];
int hed[4010],vis[4010];
int dis[4010][4010],dp[4010][4010];
int tim[4010],lim[4010],bst[4010];
int num;
int n;
void add(int u,int v,int z){++num;vet[num]=v;val[num]=z;Next[num]=hed[u];hed[u]=num;
}void dfs(int x,int dis[]){queue<int> q;q.push(x);vis[x]=x;dis[x]=0;while (!q.empty()){int u=q.front();q.pop();for (int i=hed[u];i!=-1;i=Next[i]){int v=vet[i],z=val[i];if (vis[v]!=x){vis[v]=x;dis[v]=dis[u]+z;q.push(v);}}}
}
void check(int x,int fa){for (int i=hed[x];i!=-1;i=Next[i]){int v=vet[i];if (v==fa) continue;check(v,x);}for (int i=1;i<=n;++i)if (dis[x][i]<=lim[x]){dp[x][i]=0;for (int j=hed[x];j!=-1;j=Next[j]){int v=vet[j];if (v==fa) continue;dp[x][i]+=min(dp[v][i]-tim[i],bst[v]);}dp[x][i]+=tim[i];bst[x]=min(bst[x],dp[x][i]);}
}
int main(){scanf("%d",&n);for (int i=1;i<=n;++i) scanf("%d",&tim[i]);for (int i=1;i<=n;++i) scanf("%d",&lim[i]);for (int i=1;i<=n;++i){hed[i]=-1;vis[i]=0;bst[i]=1<<29;for (int j=1;j<=n;++j) dp[i][j]=1<<29;}for (int i=1;i<n;++i){int u,v,z;scanf("%d%d%d",&u,&v,&z);add(u,v,z);add(v,u,z);}for (int i=1;i<=n;++i) dfs(i,dis[i]);check(1,0);printf("%d\n",bst[1]);return 0;
}