编程知识 购物 网址 新闻 笑话 | 软件 日历 阅读 图书馆 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
   -> C++ -> 树的重心 -> 正文阅读

[C++]树的重心

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

  
  
  
  
  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
POJ 2987 Firing
树的重心
第一章 作业7.
【左神算法课】超经典:求两单向链表交点(
上一篇文章      下一篇文章      查看所有文章
加:2017-05-06 02:44:54  更:2017-05-15 14:12:51 
 
360图书馆 软件开发资料 购物精选 新闻资讯 Chinese Culture 三丰软件 开发 中国文化 阅读网 日历 万年历 2019年10日历
2019-10-19 21:18:18
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程知识