【TYVJ】1520 树的直径
2024-08-24 05:28:29
【算法】树的直径
memset(a,0,sizeof(a))
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
struct edge{int from,v,w;}e[maxn*];
int tot,X,n,head,tail,q[maxn],d[maxn],first[maxn];
bool v[maxn];
void insert(int u,int v,int w)
{tot++;e[tot].v=v;e[tot].w=w;e[tot].from=first[u];first[u]=tot;}
void bfs(int s)
{
X=;
memset(d,,sizeof(d));
memset(v,,sizeof(v));//数组,值,范围
head=;tail=;q[]=s;v[s]=;
while(head<=tail)
{
int u=q[head++];
if(d[u]>d[X])X=u;
for(int i=first[u];i;i=e[i].from)
if(!v[e[i].v])
{
v[e[i].v]=;
d[e[i].v]=d[u]+e[i].w;
q[++tail]=e[i].v;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
insert(u,v,w);
insert(v,u,w);
}
bfs();
bfs(X);
printf("%d",d[X]);
return ;
}
最新文章
- MySQL查看数据库相关信息
- js获取url方法
- sublime text 3.0 安装 HTML-CSS-JS Prettify
- extjs 选项卡
- springmvc web应用程序 java
- Oracle 常用命令大全
- 《uname命令》-linux命令五分钟系列之五
- 高性能MySql进化论(一):数据类型的优化_上
- Thread 常搞混的几个概念sleep、wait、yield、interrupt (转)
- opencv + numpy for python
- break point
- 迅雷Vip账号共享器(持续更新)
- C#/AutoCAD 2018/ObjectArx/二次开发添加删除实体的工具函数(四)
- tf.contrib.slim
- 转载:揪出MySQL磁盘消耗迅猛的真凶
- Lombok插件
- CF1082解题报告
- HDU 2066 一个人的旅行 最短路问题
- ASP.NET Web API实践系列07,获取数据, 使用Ninject实现依赖倒置,使用Knockout实现页面元素和视图模型的双向绑定
- 29、HashSet简介