首页 > > 程序设计 > C/C++ >

树的重心

2018-06-17 22:41:03来源：未知阅读 ()

GeneralLiu

个人理解：

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

　　一个苹果从心开始烂

　　这是很糟糕的

　　一个国家从中央开始腐败

　　这也是一个道理

　　一棵树中，去掉一个点

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

　　而且不管删去哪个节点

　　剩下的节点总数是不变的

　　树的重心就可以理解为

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

　　这个节点就是重心

　　而那个最糟糕的情况

　　是指其子树中

　　　　最大子树节点最少

满足条件

　　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;
}