POJ 1985 Cow Marathon（树的直径）-白红宇的个人博客

POJ 1985 Cow Marathon（树的直径）

发布日期：2021-05-07 06:22:40 浏览次数：14 分类：技术文章

本文共 625 字，大约阅读时间需要 2 分钟。

树的直径

给定一棵树，树中每条边都有一个权值，树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。后者通常也可称为直径，即直径是一个数值概念，也可代指一条路径。

求法

先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径。可以用两次dfs先搜到1号点距离最长的点p，然后在搜到p距离最长的点w，p和w两个点的距离就是树的直径。

Cow Marathon 模板

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int d[100005], v[100005], w[100005];int first[100005], next[100005];int sum=0, ans=0;int p;void add(int x, int y, int z){   	sum++;//sum表示边的编号 	next[sum]=first[x];	first[x]=sum;	v[sum]=y;	w[sum]=z;}void dfs(int x, int father){   //father表示起点为x的边是从father到x得到的，防止从father到x后又搜索x到father 	if (ans

上一篇：POJ 2387 Til the Cows Come Home（Dijkstra优先队列）

下一篇：CSS_简介、选择器、属性和属性值、盒子模型

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章