本文共 1315 字，大约阅读时间需要 4 分钟。

医院设置的优化方法

又是一道水题。数据特别水，O(n^3)都能过，但我不会用暴力枚举的方法。我这里要讲的是一种O(n)的做法，能够在洛谷的五个数据点上实现5个0ms。

大家可以先看一下博客，但主要关注重心的求法。这里用的是加权重心，比重心更高级的一种。只需把DFS里的size[x]=1改为size[x]=dis[x]，把DFS里的size[x]*2>=n改为size[x]*2>=tot就好了（tot是所有点的权值的和）。

代码如下：

#include 
   
    #define N 420int next[N], to[N], num, head[N], size[N], dis[N], father[N], deep[N], n, ans, ans, a, b, c, tot;void add(int false_from, int false_to) {    next[++num] = head[false_from];    to[num] = false_to;    head[false_from] = num;}int dfs(int x) {    size[x] = dis[x];    for (int i = head[x]; i; i = next[i])        if (father[x] != to[i]) {            father[to[i]] = x;            dfs(to[i]);            size[x] += size[to[i]];        }    if (size[x] * 2 >= tot && !ans) ans = x;}void dfss(int x) {    anss += (deep[x] - 1) * dis[x];    for (int i = head[x]; i; i = next[i])        if (!deep[to[i]]) {            deep[to[i]] = deep[x] + 1;            dfss(to[i]);        }}int main() {    scanf("%d", &n);    for (int i = 1; i <= n; ++i) {        scanf("%d%d%d", &a, &b, &c);        dis[i] = a;        tot += a;        if (b) {            add(i, b);            add(b, i);        }        if (c) {            add(i, c);            add(c, i);        }    }    dfs(1);    deep[ans] = 1;    dfss(ans);    printf("%d", anss);    return 0;}
   

这个程序在洛谷没问题，但对其他题则需要调整数组大小。

转载自：链接