当前位置:网站首页>信息学奥赛一本通 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;
}
边栏推荐
- Common operators and operator priority
- JVMRandom不可设置种子|问题追溯|源码追溯
- 无卷积骨干网络:金字塔Transformer,提升目标检测/分割等任务精度(附源代码)...
- Some problems encountered in cocos2d-x project summary
- 秋招字节面试官问你还有什么问题?其实你已经踩雷了
- SecureRandom那些事|真伪随机数
- 微信小程序正则表达式提取链接
- Leetcode brush questions: binary tree 18 (largest binary tree)
- Elk distributed log analysis system deployment (Huawei cloud)
- 期货如何网上开户?安不安全?
猜你喜欢
JVMRandom不可设置种子|问题追溯|源码追溯
解决Thinkphp框架应用目录下数据库配置信息修改后依然按默认方式连接
秋招字节面试官问你还有什么问题?其实你已经踩雷了
2023年深圳市绿色低碳产业扶持计划申报指南
淺淺的談一下ThreadLocalInsecureRandom
Parler de threadlocal insecurerandom
Leetcode(695)——岛屿的最大面积
kubernetes资源对象介绍及常用命令(五)-(ConfigMap&Secret)
【数字IC验证快速入门】2、通过一个SoC项目实例,了解SoC的架构,初探数字系统设计流程
leetcode刷题:二叉树12(二叉树的所有路径)
随机推荐
秋招字节面试官问你还有什么问题?其实你已经踩雷了
2023年深圳市绿色低碳产业扶持计划申报指南
Database logic processing function
S7-200smart uses V90 Modbus communication control library to control the specific methods and steps of V90 servo
leetcode刷题:二叉树10(完全二叉树的节点个数)
SecureRandom那些事|真伪随机数
信息学奥赛一本通 1340:【例3-5】扩展二叉树
c語言oj得pe,ACM入門之OJ~
【数字IC验证快速入门】9、Verilog RTL设计必会的有限状态机(FSM)
DP: tree DP
B站UP搭建世界首个纯红石神经网络、基于深度学习动作识别的色情检测、陈天奇《机器学编译MLC》课程进展、AI前沿论文 | ShowMeAI资讯日报 #07.05
深度學習 卷積神經網絡(CNN)基礎
Guidelines for application of Shenzhen green and low carbon industry support plan in 2023
Debezium series: modify the source code to support drop foreign key if exists FK
挖财钱堂教育靠谱安全吗?
618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
Thread pool parameters and reasonable settings
ByteDance dev better technology salon was successfully held, and we joined hands with Huatai to share our experience in improving the efficiency of web research and development
Go language learning tutorial (16)
Hong Kong stocks will welcome the "best ten yuan store". Can famous creative products break through through the IPO?