1338：【例3-3】医院设置

【题目描述】
设有一棵二叉树（如下图），其中圈中的数字表示结点中居民的人口，圈边上数字表示结点编号。现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻结点之间的距离为1。就本图而言，若医院建在1处，则距离和=4+12+2×20+2×40=136；若医院建在3处，则距离和=4×2+13+20+40=81……

【输入】
第一行一个整数n，表示树的结点数（n≤100）。接下来的n行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为0表示无链接；第三个数为右链接，为0表示无链接。

【输出】
一个整数，表示最小距离和。

【输入样例】
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
【输出样例】
81

分析

1. 由于此题n的数据范围比较小，我们可以把这个题当做图来处理，用邻接矩阵去存储图，然后通过Floyd算法求得每点之间的最短路径；然后枚举每一个节点，设为可能建立医院，然后计算其距离和sum，与ans比较，存储较小的；g[i][j]表示编号i到编号j的这条边的权值（如果两个结点有边，默认为1），a[i]表示编号为i这结点的值（居民人口）；参考：1338：【例3-3】医院设置
2. 也可以采用通过结构体来存储结点，通过dfs也就是递归的去求距离；毕竟树的问题挺多都是递归去处理解决的；参考：信息学奥赛一本通 1338：【例3-3】医院设置、信息学奥赛一本通评测系统P1338【例3-3】医院设置

邻接矩阵+Floyd

#include 

using namespace std;

const int N = 105, INF = 0x3f3f3f3f;
int g[N][N], a[N];
int n, ans = INF;

void floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}

int main() {
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j)
                g[i][j] = 0;
            else
                g[i][j] = INF;
        }
    }
    int l, r;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> l >> r;
        if (l)
            g[i][l] = g[l][i] = 1;
        if (r)
            g[i][r] = g[r][i] = 1;
    }
    floyd();
    for (int i = 1; i <= n; ++i) {
        int sum = 0;
        for (int j = 1; j <= n; ++j) {
            sum += g[i][j] * a[j];
        }
        ans = min(ans, sum);
    }
    cout << ans;
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

结构体数组+dfs

1. 枚举每个点作为医院建设点，然后从这个点开始搜索。计算当前这个点做医院的距离和，在搜完和ans比较后取小的；
2. 搜索过程，我们两个参数：u和d表示 当前在编号为u这个结点，当前结点u离医院的距离为d；然后从当前点向别的点搜索的条件：当前这个结点没有计算过而且不能为空；这样计算完sum，依次搜索u的双亲、左孩子、右孩子，就不用去判断是否存在；

#include 

using namespace std;
struct Node {
    int left, right, parent, val;//左孩子，右孩子，双亲，居民数

};
const int N = 105, INF = 0x3f3f3f3f;
Node node[N];
int n, ans = INF, sum;
int vis[N];

//当前在编号为u这个结点，当前结点u离医院的距离为d
void dfs(int u, int d) {
    //当前这个结点没有计算过而且不能为空
    if (vis[u] || u == 0)
        return;
    sum += node[u].val * d;
    vis[u] = 1;
    dfs(node[u].parent, d + 1);
    dfs(node[u].left, d + 1);
    dfs(node[u].right, d + 1);
}


int main() {
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> node[i].val;
        cin >> node[i].left;
        cin >> node[i].right;
        //node[i]的孩子不为空的话，把孩子的双亲设置为i
        if (node[i].left)
            node[node[i].left].parent = i;
        if (node[i].right)
            node[node[i].right].parent = i;
    }
    //枚举每个点作为医院建设点
    for (int i = 1; i <= n; ++i) {
        dfs(i, 0);
        ans = min(sum, ans);
        memset(vis, 0, sizeof vis);
        sum = 0;
    }
    cout << ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48