A28687. 某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有n个节点，编号分别为1、2、3、.... n。为了实时记录道路情况，需要在某些节点部署监控设备，当部署好后，与该节点直接相连的所有道路均能被监控到。为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。给定每个节点部署监控设备的费用…
填空题
困难
知识点
题目描述
题目描述
某城市的道路构成了一个巨大的树形结构，每一条道路可视为该结构的一条边，而道路的交叉点或端点视为其中的一个节点。该城市共有n个节点，编号分别为1、2、3、.... n。为了实时记录道路情况，需要在某些节点部署监控设备，当部署好后，与该节点直接相连的所有道路均能被监控到。
为了优化资源分配，在保证整座城市的所有道路都被监控到的前提下，部署监控设备的费用要尽可能少。
给定每个节点部署监控设备的费用，请计算要使所有道路都能被监控到的最少花费是多少?
例如: n=8,表示有8个节点(即道路交叉点或端点)，1到8号节点部署监控设备的费用分别为33、12、 30、22、 18、 10、31、28。道路分布图如下:
根据观察可得，在2号和3号节点处部署监控设备，可以使所有道路都能被监控到，并且花费最少，最少花费为42。
输入格式
第一行输入一个整数n (2≤n≤104) ，表示城市中节点(即道路交叉点或端点)的数量
第二行输入n个整数(1<整数≤105) ，分别表示1号到n号节点部署监控设备的费用
接下来n-1行，每行输入两个整数a, b,表示节点a和节点b之间有一条道路
输出格式
输出一个整数，表示要使所有道路均能被监控到的最少花费。
输入样例
8
33 12 30 22 18 10 31 28
1 2
1 3
2 4
2 5
2 6
3 7
3 8输出样例
42参考答案
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int n,w[N]; //n：（节点）的总数。w[N]：一个数组，存储每个节点的花费。
vector<int> e[N]; //e[N]：一个邻接表，用于存储树的边，即节点的父子关系。
int f[N][2];
/*f[N][2]：一个二维DP数组，
其中f[u][0]代表不选当前节点以i为根的子树最小花费
f[i][1]代表选当前节点以i为根的子树最小花费*/
void dfs(int u,int fa)//这是一个深度优先搜索（DFS）函数，用于遍历以u为根的子树，并计算f[u][0]和f[u][1]的值。fa表示u的父亲节点，用于避免在递归时向上遍历到父节点。
{
f[u][1]=w[u]; //首先，将f[u][1]初始化为w[u]，因为如果u选择，那么他的花费一定会被计入。
for(auto v:e[u]) //然后，遍历u的所有子节点v（通过e[u]）。对于每个子节点，首先进行DFS，计算f[v][0]和f[v][1]的值。
{
if(v==fa)continue;
dfs(v,u);
/*
更新f[u][0]和f[u][1]的值。如果u不选，那么子节点v可以自由选择是否参加，
所以f[u][0]应加上所有子节点的花费（即f[v][1]）。
如果u选择，那么子节点v不能同时选，
所以f[u][1]应加上所有子节点中“参加或不参加”的花费中的较小值（即min(f[v][1], f[v][0])）。
*/
f[u][0]+=f[v][1];
f[u][1]+=min(f[v][1],f[v][0]);
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i]; //输入节点花费
}
for(int i=1;i<n;i++) //读取节点的父子关系（即树的边），并将它们添加到邻接表e中。
{
int a,b;
cin>>a>>b;
e[a].push_back(b);
e[b].push_back(a);
}
dfs(1,-1); //从根节点（假设为1）开始遍历整棵树，并计算所有f[u][0]和f[u][1]的值。
cout<<min(f[1][0],f[1][1])<<endl; //输出结果
return 0;
}
上一题
下一题