题目描述

要求建立医院的位置，到其余所有点的距离最小

样例

时间复杂度 $O(n^2)$

思路：数据范围并不大，所以直接枚举一下每个点当做医院，计算其余点到当前点的距离，取最小值就好了

要点：

1. 如何存下来这个树？—— 直接用邻接表，模板嘛
2. 如果求其他点到医院的位置？——DFS过程中，记录当前枚举到了第几个点，然后求出来子树到当前点的距离

综上，需要枚举n个点，对每个点都要算一遍距离，所以是 $O(n^2)$的

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110, M = N * 2, INF = 1e9;

int n;
int cnt[N]; // 存下每个点住了多少个人
int h[N], e[M], ne[M], idx;

// 加边
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// father表示你从哪个点来的，dist 表示距离根节点的距离是多少
int dfs(int u, int father, int dist) 
{
    int sum = cnt[u] * dist; // 计算当前点到根节点的距离是多少

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue; // 保证只往下搜

        sum += dfs(j, u, dist + 1);
    }

    return sum;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i ++ )
    {
        int l, r;
        cin >> cnt[i] >> l >> r; // 输入人数、左右儿子
        if (l) add(i, l), add(l, i); // 加上两条边， 成为无向图
        if (r) add(i, r), add(r, i);
    }

    int res = INF;

    for (int i = 1; i <= n; i ++ ) res = min(res, dfs(i, -1, 0));

    cout << res << endl;

    return 0;
}