树的重心

2017-05-06 02:39

树的重心0

 

 

 

 

个人理解:

  

  

  重心 应该可以 当成 "中央" 来理解吧

  

  一个苹果 从 心 开始烂

  这是很糟糕的

  

  一个国家 从 中央 开始腐败

  这也是一个道理

 

  一棵树中, 去掉一个点

  一定会 分成几块 导致不联通 (叶子 和 只有一个孩子 的根 当然是暂时不考虑了)

  而且 不管删去 哪个节点

  剩下的 节点总数 是不变的

  

  树的重心 就可以理解为

  删去某节点  使 剩下节点块 变成最糟糕 的情况

  这个节点 就是重心

  

  而那个 最糟糕的情况

  是指 其子树中 

    最大子树  节点最少

  

 

 

满足条件

  

  size[i]*2>=n,

  且 他的 子树 size[j]*2<n

  

  如果 n 为偶数 重心可能会有 两个

 

  具体怎么证明  我也不清楚

  总之 , 玄学 地 去理解吧

 

 

应用

 

 

  洛谷 P1364 医院设置

 

  题目大意

    

    给出 一个树型 城市

    每个 居住点 都有一定人数

    道路 的 长度 均为 1

    现在 要建一家 医院

    使 所以居民 行走的路程和 最小

 

  加权重心可求

#include<bits/stdc++.h>
using namespace std;
int size[105],ans,dis[105],tot,s,n,vec[105][3],a[105];
void dfs(int k){ // 找 重心
 size[k]=a[k];
 if(vec[k][0])
 dfs(vec[k][0]),
 size[k]+=size[vec[k][0]];
 if(vec[k][1])
 dfs(vec[k][1]),
 size[k]+=size[vec[k][1]];
 if(!s&&size[k]*2>tot)s=k; //如果满足加权重心条件 则将第一个满足条件的 设为重心
}
void dfs1(int k){ // 求 距离
 for(int i=0;i<=2;i++)
 if(vec[k][i]&&!dis[vec[k][i]]){
 dis[vec[k][i]]=dis[k]+1;
 ans+=a[vec[k][i]]*(dis[vec[k][i]]-1);
 dfs1(vec[k][i]);
 }
}
int main(){
 cin>>n;
 for(int i=1;i<=n;i++){ //因为是二叉树,所以vec数组只存 左 右孩子 及 父亲即可
 cin>>a[i]>>vec[i][0]>>vec[i][1];
 tot+=a[i]; //累加权值
 vec[vec[i][0]][2]=i;
 vec[vec[i][1]][2]=i;
 }
 dfs(1); //认为 1 为树根, 找加权重心 s
 dis[s]=1;
 dfs1(s); // 二次 dfs 累加 ans
 cout<<ans;
 return 0;
}