P1364 医院设置

医院设置

又是一道水题。

洛谷链接。

洛谷上的数据特别水，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是所有点的权值的和）。

代码：

 1 #include<cstdio>
 2 #define N 420
 3 int next[N],to[N],num,head[N],size[N],dis[N],father[N],deep[N],n,ans,anss,a,b,c,tot;
 4 void add(int false_from,int false_to){
 5     next[++num]=head[false_from];
 6     to[num]=false_to;
 7     head[false_from]=num;
 8 }
 9 int dfs(int x){
10     size[x]=dis[x];
11     for(int i=head[x];i;i=next[i])
12         if(father[x]!=to[i]){
13             father[to[i]]=x;
14             dfs(to[i]);
15             size[x]+=size[to[i]];
16         }
17     if(size[x]*2>=tot&&!ans)
18         ans=x;
19 }
20 void dfss(int x){
21     anss+=(deep[x]-1)*dis[x];
22     for(int i=head[x];i;i=next[i])
23         if(!deep[to[i]]){
24             deep[to[i]]=deep[x]+1;
25             dfss(to[i]);
26         }
27 }
28 int main(){
29     scanf("%d",&n);
30     for(int i=1;i<=n;++i){
31         scanf("%d%d%d",&a,&b,&c);
32         dis[i]=a;
33         tot+=a;
34         if(b){
35             add(i,b);
36             add(b,i);
37         }
38         if(c){
39             add(i,c);
40             add(c,i);
41         }
42     }
43     dfs(1);
44     deep[ans]=1;
45     dfss(ans);
46     printf("%d",anss);
47     return 0;
48 }

View Code

当然，这个程序A洛谷没问题，但是搞别的题就需要把数组开大一些了。