【洛谷 P1364】医院设置 题解（图论+深度优先搜索）

医院设置

题目描述

设有一棵二叉树，如图：

其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 $1$。如上图中，若医院建在 $1$ 处，则距离和 $=4+12+2\times 20+2\times 40=136$；若医院建在 $3$ 处，则距离和 $=4\times 2+13+20+40=81$。

输入格式

第一行一个整数 $n$，表示树的结点数。

接下来的 $n$ 行每行描述了一个结点的状况，包含三个整数 $w,u,v$，其中 $w$ 为居民人口数，$u$ 为左链接（为 $0$ 表示无链接），$v$ 为右链接（为 $0$ 表示无链接）。

输出格式

一个整数，表示最小距离和。

样例 #1

样例输入 #1

5						
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
1
2
3
4
5
6

样例输出 #1

81
1

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 100$，$0\le u,v\le n$，$1\le w\le 10^5$。

---

思路

将二叉树储存为一张图，存图时要存双向边。

暴力枚举每个节点作为医院，然后分别计算所有节点到这个医院的距离的加权和。

使用 DFS 遍历整张图，对于当前遍历的节点 $x$，用一个变量 $sum$ 记录所有已经遍历的节点到当前节点 $x$ 的距离的加权和，用一个 bitset 变量 $vis$ 记录所有已经遍历过的节点，然后递归地遍历 $x$ 的所有邻接节点，计算它们到 $x$ 的距离的加权和，并将其加到 $sum$ 上。

为了避免重复遍历已经遍历过的节点，并方便计算节点到达医院的距离，需要在遍历之前将 $vis[x]$ 设为 $1$，在遍历之后再将其设为 $0$。

遍历完所有的节点后，用一个变量 $ans$ 记录所有节点作为医院时的最小距离和，然后每次更新 $ans=\min (ans,sum)$。最后输出 $ans$ 即可。

---

AC代码

#include 
#include 
#include 
#include 
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 1005;

// 链式前向星
struct Sedge
{
    int to;
    int next;
} edge[N];
int head[N];
int cnt = 0;
int w[N];

int n;
int tmp;
int sum;
int ans;

bitset<N> vis;

void add(int u, int v)
{
    if (u && v)
    {
        edge[cnt].to = v;
        edge[cnt].next = head[u];
        head[u] = cnt++;
    }
}

void dfs(int x)
{
    if (vis[x])
    {
        return;
    }
    sum += w[x] * vis.count();
    // cout << x << endl;
    vis[x] = 1;
    for (int i = head[x]; ~i; i = edge[i].next)
    {
        dfs(edge[i].to);
    }
    vis[x] = 0;
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> w[i] >> a >> b;
        add(i, a);
        add(i, b);
        add(a, i);
        add(b, i);
    }
    for (int i = 1; i <= n; i++)
    {
        sum = 0;
        vis.reset();
        dfs(i);
        if (1 == i)
        {
            ans = sum;
        }
        else
        {
            ans = min(ans, sum);
        }
        // cout << sum << endl;
    }
    cout << ans << endl;
    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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84