Informatics Olympiad 1338: [example 3-3] hospital setting | Luogu p1364 hospital setting

【 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)$

solution 2： The center of gravity of the tree

The complexity is $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;
}