当前位置:网站首页>Informatics Olympiad 1338: [example 3-3] hospital setting | Luogu p1364 hospital setting
Informatics Olympiad 1338: [example 3-3] hospital setting | Luogu p1364 hospital setting
2022-07-05 20:17:00 【Jun Yi_ noip】
【 Topic link 】
ybt 1338:【 example 3-3】 Hospital settings
Luogu P1364 Hospital settings
【 Topic test site 】
1. Binary tree
- Binary tree with pointer to parent node
There are not only pointers to left and right children in the nodes of the tree , There are also pointers to parent nodes
2. chart
The storage structure of the graph :
- Adjacency matrix
- Adjacency list
Graph traversal :
- Depth-first traversal
- Breadth first traversal
【 Their thinking 】
solution 1: enumeration
Enumerate attempts to build hospitals at each node . After determining to build a hospital at a node , Start from this node to do depth or breadth first traversal , Every time we traverse to a new node , Add the sum to the value on this node ( Number of residents ) Multiply by the distance from the node to the node where the hospital is located . After the search is over , The total sum is the sum of the distance the residents have traveled to the hospital at this location .
Calculate the sum of the residents' journey after building the hospital at each node , Compare and output the minimum value .
Storage structure , You can use binary trees with pointers to parent nodes , You can also use the storage structure of the graph : Adjacency matrix or adjacency table .
Because the graph is a tree structure , During the search process, the last searched node can be passed in as a parameter , Therefore, you can not search the visited nodes , So there is no need to set vis Array .
The complexity of the algorithm is O ( n 2 ) O(n^2) O(n2)
solution 2: The center of gravity of the tree
The complexity is O ( n ) O(n) O(n)
( To be improved )
【 Solution code 】
solution 1: enumeration
- How to write it 1: Binary tree with pointer to parent node
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
struct Node
{
int val;// Number of residents
int left, right, parent;// Left the child , The right child , Parents
};
Node node[N];
int sum;//sum: Residents' journey and
// From fr Node search to k node , The first k The distance from the node to the hospital is d, Ask the residents for the distance and
void dfs(int k, int d, int fr)
{
sum += node[k].val*d;// The total distance plus the number of residents on the node times the distance to the hospital
int p[3] = {
node[k].parent, node[k].left, node[k].right};// take 3 There is an array of addresses that may be accessed next p in .
for(int i = 0; i < 3; ++i)
{
if(p[i] != 0 && p[i] != fr)// From fr Node search to k node , You can't start from k Node search to fr node
dfs(p[i], d + 1, k);
}
}
int main()
{
int n, val, left, right, ans = INF;
cin >> n;
for(int i = 1; i <= n; ++i)// The first i Node number is stored in node[i]
{
cin >> val >> left >> right;
node[i].val = val;// Set up i node
node[i].left = left;
node[i].right = right;
if(left != 0)// take i The parents of the children around the node are set to 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);// At node i Build a hospital , A distance of 0 The previous node does not exist , fill 0 that will do .
ans = min(ans, sum);// Find the minimum value of the sum of residents' distances
}
cout << ans;
return 0;
}
- How to write it 2: Adjacency matrix + Deep search
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
bool edge[N][N];
int val[N];//val[i]: The first i Number of residents at the top
int n, sum;//sum: Residents' journey and
// From fr Vertex search to k The vertices , The first k The distance from the vertex to the hospital is d, Ask the residents for the distance and
void dfs(int k, int d, int fr)
{
sum += val[k]*d;// The total distance plus the number of residents on the vertex times the distance to the hospital
for(int i = 1; i <= n; ++i)
{
if(edge[k][i] && i != fr)// From fr Node search to k node , You can't start from k Node search to fr node
dfs(i, d + 1, k);
}
}
int main()
{
int l, r, ans = INF;
cin >> n;
for(int i = 1; i <= n; ++i)// The first i Node number is stored in node[i]
{
cin >> val[i] >> l >> r;//i My left child is l, The right child is r, Equivalent to having edges (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);// At the top i Build a hospital , A distance of 0 The previous vertex does not exist , fill 0 that will do .
ans = min(ans, sum);// Find the minimum value of the sum of residents' distances
}
cout << ans;
return 0;
}
- How to write it 3: Adjacency list + Guang Shu
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define INF 0x3f3f3f3f
struct Node
{
int f, t, d;// from f To search the t,d: distance
Node(){
}
Node(int a, int b, int c):f(a), t(b), d(c){
}
};
vector<int> edge[N];
int n, val[N];//val[i]: The first i Number of residents at the top
int bfs(int st)
{
int sum = 0;//sum: Residents' journey and
queue<Node> que;
que.push(Node(0, st, 0));// from 0 To st, Starting steps 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)// from u.f To search the u.t, No more from u.t Search back u.f
que.push(Node(u.t, v, u.d + 1));// from u.t To v, The steps are u.d+1
}
}
return sum;
}
int main()
{
int l, r, ans = INF;
cin >> n;
for(int i = 1; i <= n; ++i)// The first i Node number is stored in node[i]
{
cin >> val[i] >> l >> r;//i My left child is l, The right child is r, Equivalent to having edges (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));// Find the minimum value of the sum of residents' distances
cout << ans;
return 0;
}
边栏推荐
猜你喜欢
Introduction to dead letter queue (two consumers, one producer)
[Yugong series] go teaching course in July 2022 004 go code Notes
Unity editor extended UI control
无卷积骨干网络:金字塔Transformer,提升目标检测/分割等任务精度(附源代码)...
IC科普文:ECO的那些事儿
微信小程序正则表达式提取链接
Practical demonstration: how can the production research team efficiently build the requirements workflow?
Solve the problem that the database configuration information under the ThinkPHP framework application directory is still connected by default after modification
Station B up builds the world's first pure red stone neural network, pornographic detection based on deep learning action recognition, Chen Tianqi's course progress of machine science compilation MLC,
leetcode刷题:二叉树12(二叉树的所有路径)
随机推荐
Oracle tablespace management
Mysql频繁操作出现锁表问题
Leetcode skimming: binary tree 16 (path sum)
秋招字节面试官问你还有什么问题?其实你已经踩雷了
B站UP搭建世界首个纯红石神经网络、基于深度学习动作识别的色情检测、陈天奇《机器学编译MLC》课程进展、AI前沿论文 | ShowMeAI资讯日报 #07.05
1:引文;
Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
About the priority of Bram IP reset
Minimum commission for stock trading account opening, where to open an account with low commission? Is it safe to open an account on your mobile phone
[Yugong series] go teaching course in July 2022 004 go code Notes
中金财富在网上开户安全吗?
[quick start of Digital IC Verification] 6. Quick start of questasim (taking the design and verification of full adder as an example)
Database logic processing function
【c语言】归并排序
C langue OJ obtenir PE, ACM démarrer OJ
炒股开户最低佣金,低佣金开户去哪里手机上开户安全吗
DP:树DP
C - sequential structure
BZOJ 3747 POI2015 Kinoman 段树
Debezium series: idea integrates lexical and grammatical analysis ANTLR, and check the DDL, DML and other statements supported by debezium