当前位置:网站首页>信息学奥赛一本通 1338:【例3-3】医院设置 | 洛谷 P1364 医院设置
信息学奥赛一本通 1338:【例3-3】医院设置 | 洛谷 P1364 医院设置
2022-07-05 20:10:00 【君义_noip】
【题目链接】
ybt 1338:【例3-3】医院设置
洛谷 P1364 医院设置
【题目考点】
1. 二叉树
- 带指向双亲结点指针的二叉树
树的结点中不但有指向左右孩子的指针,也有指向双亲结点的指针
2. 图
图的存储结构:
- 邻接矩阵
- 邻接表
图的遍历:
- 深度优先遍历
- 广度优先遍历
【解题思路】
解法1:枚举
枚举尝试在每个结点建医院。确定在一个结点建医院后,从这个结点开始做深度或广度优先遍历,每遍历到一个新的结点,总加和加上该结点上数值(居民数)乘以该结点到医院所在结点的距离。搜索结束后,总加和即为居民到这位置的医院所走路程之和。
求出在每个结点建医院后得到的居民所走路程之和,比较并输出其中的最小值。
存储结构,可以使用带指向双亲结点指针的二叉树,也可以使用图的存储结构:邻接矩阵或邻接表。
由于该图是树型结构,搜索的过程中可以把上一次搜索到的结点当做参数传入,因而可以不搜到已经访问过的结点,所以不需要设vis数组。
该算法复杂度为 O ( n 2 ) O(n^2) O(n2)
解法2:树的重心
复杂度为 O ( n ) O(n) O(n)
(待完善)
【题解代码】
解法1:枚举
- 写法1:带有指向双亲结点指针的二叉树
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
struct Node
{
int val;//居民数
int left, right, parent;//左孩子,右孩子,双亲
};
Node node[N];
int sum;//sum:居民路程和
//从第fr结点搜索到第k结点,第k结点到医院的距离为d,求居民路程和
void dfs(int k, int d, int fr)
{
sum += node[k].val*d;//总路程加上该结点上居民数乘以到医院的距离
int p[3] = {
node[k].parent, node[k].left, node[k].right};//将3个下一次可能访问到的地址存在数组p中。
for(int i = 0; i < 3; ++i)
{
if(p[i] != 0 && p[i] != fr)//从第fr结点搜索到第k结点,不能再从第k结点搜索到第fr结点
dfs(p[i], d + 1, k);
}
}
int main()
{
int n, val, left, right, ans = INF;
cin >> n;
for(int i = 1; i <= n; ++i)//第i号结点存储在node[i]
{
cin >> val >> left >> right;
node[i].val = val;//设置i结点
node[i].left = left;
node[i].right = right;
if(left != 0)//将i结点左右孩子的双亲设为i
node[left].parent = i;
if(right != 0)
node[right].parent = i;
}
for(int i = 1; i <= n; ++i)
{
sum = 0;
dfs(i, 0, 0);//在结点i建医院,距离为0 前一个结点不存在,填0即可。
ans = min(ans, sum);//求居民路程加和的最小值
}
cout << ans;
return 0;
}
- 写法2:邻接矩阵+深搜
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
bool edge[N][N];
int val[N];//val[i]:第i顶点的居民数
int n, sum;//sum:居民路程和
//从第fr顶点搜索到第k顶点,第k顶点到医院的距离为d,求居民路程和
void dfs(int k, int d, int fr)
{
sum += val[k]*d;//总路程加上该顶点上居民数乘以到医院的距离
for(int i = 1; i <= n; ++i)
{
if(edge[k][i] && i != fr)//从第fr结点搜索到第k结点,不能再从第k结点搜索到第fr结点
dfs(i, d + 1, k);
}
}
int main()
{
int l, r, ans = INF;
cin >> n;
for(int i = 1; i <= n; ++i)//第i号结点存储在node[i]
{
cin >> val[i] >> l >> r;//i的左孩子是l,右孩子是r,相当于有边(i,l),(i,r)
edge[i][l] = edge[l][i] = true;
edge[i][r] = edge[r][i] = true;
}
for(int i = 1; i <= n; ++i)
{
sum = 0;
dfs(i, 0, 0);//在顶点i建医院,距离为0 前一个顶点不存在,填0即可。
ans = min(ans, sum);//求居民路程加和的最小值
}
cout << ans;
return 0;
}
- 写法3:邻接表+广搜
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
struct Node
{
int f, t, d;//从f搜索到的t,d:距离
Node(){
}
Node(int a, int b, int c):f(a), t(b), d(c){
}
};
vector<int> edge[N];
int n, val[N];//val[i]:第i顶点的居民数
int bfs(int st)
{
int sum = 0;//sum:居民路程和
queue<Node> que;
que.push(Node(0, st, 0));//从0到st,起始步数0
while(que.empty() == false)
{
Node u = que.front();
que.pop();
sum += val[u.t]*u.d;
for(int i = 0; i < edge[u.t].size(); ++i)
{
int v = edge[u.t][i];
if(v != u.f)//从u.f搜索到的u.t,不能再从u.t搜索回u.f
que.push(Node(u.t, v, u.d + 1));//从u.t到v,步数为u.d+1
}
}
return sum;
}
int main()
{
int l, r, ans = INF;
cin >> n;
for(int i = 1; i <= n; ++i)//第i号结点存储在node[i]
{
cin >> val[i] >> l >> r;//i的左孩子是l,右孩子是r,相当于有边(i,l),(i,r)
if(l != 0)
{
edge[i].push_back(l);
edge[l].push_back(i);
}
if(r != 0)
{
edge[i].push_back(r);
edge[r].push_back(i);
}
}
for(int i = 1; i <= n; ++i)
ans = min(ans, bfs(i));//求居民路程加和的最小值
cout << ans;
return 0;
}
边栏推荐
猜你喜欢
Leetcode: binary tree 15 (find the value in the lower left corner of the tree)
leetcode刷题:二叉树14(左叶子之和)
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
Redis cluster simulated message queue
js实现禁止网页缩放(Ctrl+鼠标、+、-缩放有效亲测)
SecureRandom那些事|真伪随机数
深度学习 卷积神经网络(CNN)基础
leetcode刷题:二叉树16(路径总和)
2023年深圳市绿色低碳产业扶持计划申报指南
随机推荐
Notes on key vocabulary in the English original of the biography of jobs (12) [chapter ten & eleven]
《乔布斯传》英文原著重点词汇笔记(十二)【 chapter ten & eleven】
基础篇——配置文件解析
The difference between ID selector and class selector
信息学奥赛一本通 1337:【例3-2】单词查找树 | 洛谷 P5755 [NOI2000] 单词查找树
Leetcode brush questions: binary tree 11 (balanced binary tree)
Tasks in GStreamer
微信小程序正则表达式提取链接
What is PyC file
c語言oj得pe,ACM入門之OJ~
Securerandom things | true and false random numbers
[C language] string function and Simulation Implementation strlen & strcpy & strcat & StrCmp
Leetcode brush question: binary tree 13 (the same tree)
Thread pool parameters and reasonable settings
95后阿里P7晒出工资单:狠补了这个,真香...
Common operators and operator priority
中金财富在网上开户安全吗?
【数字IC验证快速入门】9、Verilog RTL设计必会的有限状态机(FSM)
深度学习 卷积神经网络(CNN)基础
Elk distributed log analysis system deployment (Huawei cloud)