信息学奥赛一本通 1338：【例3-3】医院设置 | 洛谷 P1364 医院设置

【题目链接】

ybt 1338：【例3-3】医院设置
洛谷 P1364 医院设置

【题目考点】

1. 二叉树

• 带指向双亲结点指针的二叉树
  树的结点中不但有指向左右孩子的指针，也有指向双亲结点的指针

2. 图

图的存储结构：

• 邻接矩阵
• 邻接表

图的遍历：

• 深度优先遍历
• 广度优先遍历

【解题思路】

解法1：枚举

枚举尝试在每个结点建医院。确定在一个结点建医院后，从这个结点开始做深度或广度优先遍历，每遍历到一个新的结点，总加和加上该结点上数值（居民数）乘以该结点到医院所在结点的距离。搜索结束后，总加和即为居民到这位置的医院所走路程之和。
求出在每个结点建医院后得到的居民所走路程之和，比较并输出其中的最小值。
存储结构，可以使用带指向双亲结点指针的二叉树，也可以使用图的存储结构：邻接矩阵或邻接表。
由于该图是树型结构，搜索的过程中可以把上一次搜索到的结点当做参数传入，因而可以不搜到已经访问过的结点，所以不需要设vis数组。
该算法复杂度为$O(n^2)$

解法2：树的重心

复杂度为$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;
}