搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

【学习笔记】[图论]树的直径

[复制链接]
查看: 39|回复: 0

1万

主题

1万

帖子

4万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
45261
发表于 2020-2-14 23:19 | 显示全部楼层 |阅读模式
非严酷界说:在一棵带权树上,相聚间隔最大的两个点最长链的长度,称之为树的直径
样例输入:
  1. 41 2 101 3 121 4 15
复制代码
样例输出
  1. 27
复制代码
似乎并没有什么难大白的地方。
解法1:DP
咕着
解法2:DFS
经过思考,发现一个严重的性质:离树上的某一结点最远的那个结点,定是直径的一个端点。
那末就好办了!找到任一点的最远点,再找到这个最远点的远点,这条途径就是树的直径。所以必要两次 DFS 。
[code]#include #include #include const int N=1000010;using namespace std;int n,m,head[N],tot,dis[N],cur,mx;//mx是最远间隔struct Edge{    int to,next,val;};Edge G[N
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 全椒百姓网-全椒知名**,发布及时新鲜的全椒新闻资讯 生活信息 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表