如何制作网站模板,怎样营销网站建设,连江县建设局网站,开发软件难吗医院设置
题目描述
设有一棵二叉树#xff0c;如图#xff1a; 其中#xff0c;圈中的数字表示结点中居民的人口。圈边上数字表示结点编号#xff0c;现在要求在某个结点上建立一个医院#xff0c;使所有居民所走的路程之和为最小#xff0c;同时约定#xff0c;相邻接…医院设置
题目描述
设有一棵二叉树如图 其中圈中的数字表示结点中居民的人口。圈边上数字表示结点编号现在要求在某个结点上建立一个医院使所有居民所走的路程之和为最小同时约定相邻接点之间的距离为 1 1 1。如上图中若医院建在 1 1 1 处则距离和 4 12 2 × 20 2 × 40 136 4122\times202\times40136 4122×202×40136若医院建在 3 3 3 处则距离和 4 × 2 13 20 40 81 4\times213204081 4×213204081。
输入格式
第一行一个整数 n n n表示树的结点数。
接下来的 n n n 行每行描述了一个结点的状况包含三个整数 w , u , v w, u, v w,u,v其中 w w w 为居民人口数 u u u 为左链接为 0 0 0 表示无链接 v v v 为右链接为 0 0 0 表示无链接。
输出格式
一个整数表示最小距离和。
样例 #1
样例输入 #1
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0样例输出 #1
81提示
数据规模与约定
对于 100 % 100\% 100% 的数据保证 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100 0 ≤ u , v ≤ n 0 \leq u, v \leq n 0≤u,v≤n 1 ≤ w ≤ 1 0 5 1 \leq w \leq 10^5 1≤w≤105。 思路
将二叉树储存为一张图存图时要存双向边。
暴力枚举每个节点作为医院然后分别计算所有节点到这个医院的距离的加权和。
使用 DFS 遍历整张图对于当前遍历的节点 x x x用一个变量 s u m sum sum 记录所有已经遍历的节点到当前节点 x x x 的距离的加权和用一个 bitset 变量 v i s vis vis 记录所有已经遍历过的节点然后递归地遍历 x x x 的所有邻接节点计算它们到 x x x 的距离的加权和并将其加到 s u m sum sum 上。
为了避免重复遍历已经遍历过的节点并方便计算节点到达医院的距离需要在遍历之前将 v i s [ x ] vis[x] vis[x] 设为 1 1 1在遍历之后再将其设为 0 0 0。
遍历完所有的节点后用一个变量 a n s ans ans 记录所有节点作为医院时的最小距离和然后每次更新 a n s min ( a n s , s u m ) ans\min(ans,sum) ansmin(ans,sum)。最后输出 a n s ans ans 即可。 AC代码
#include iostream
#include bitset
#include algorithm
#include cstring
#define AUTHOR HEX9CF
using namespace std;const int N 1005;// 链式前向星
struct Sedge
{int to;int next;
} edge[N];
int head[N];
int cnt 0;
int w[N];int n;
int tmp;
int sum;
int ans;bitsetN vis;void add(int u, int v)
{if (u v){edge[cnt].to v;edge[cnt].next head[u];head[u] cnt;}
}void dfs(int x)
{if (vis[x]){return;}sum w[x] * vis.count();// cout x endl;vis[x] 1;for (int i head[x]; ~i; i edge[i].next){dfs(edge[i].to);}vis[x] 0;
}int main()
{memset(head, -1, sizeof(head));cin n;for (int i 1; i n; i){int a, b;cin w[i] a b;add(i, a);add(i, b);add(a, i);add(b, i);}for (int i 1; i n; i){sum 0;vis.reset();dfs(i);if (1 i){ans sum;}else{ans min(ans, sum);}// cout sum endl;}cout ans endl;return 0;
}
