树的直径 poj 2631
2024-10-20 08:33:49
树的直径:从随意一点出发,BFS找到最远的距离,然后在从该点出发BFS找到最远的距离
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <deque>
#include <vector>
using namespace std;
const int maxn = 10008;
const int inf = 0x3ffffff;
struct Node {
int w, next,to;
Node (int x = 0, int y = 0,int u = 0 ){
to = x;w = y;next = u;
}
}e[maxn*4];
int d[maxn],head[maxn],tot;
void add(int u,int v,int w){
e[tot] = Node(v,w,head[u]);
head[u] = tot++;
e[tot] = Node(u,w,head[v]);
head[v] = tot++;
}
int BFS(int u) {
memset(d,-1,sizeof(d));
d[u] = 0;
int max_int = 0,id = u;
queue <int> q;
q.push(u);
while(!q.empty()){
u = q.front();q.pop();
if(d[u] > max_int) {
max_int = d[u];
id = u;
} for(int i=head[u];i!=-1;i=e[i].next){
if(d[e[i].to] == -1){
d[e[i].to] = d[u] + e[i].w;
q.push(e[i].to);
}
}
}
// cout << id <<endl;
return id;
}
int main(){
int u,v,w; //freopen("input.txt","r",stdin);
memset(head,-1,sizeof(head));
tot = 0;
while(scanf("%d%d%d",&u,&v,&w) == 3)add(u,v,w);
printf("%d\n",d[BFS(BFS(u))]);
return 0;
}
最新文章
- Codeforces Round #341 Div.2 D. Rat Kwesh and Cheese
- OA项目笔记-从建立接口 dao impl action jsp等框架实现crud
- 简单几何(线段相交) POJ 1410 Intersection
- java 调用grads 自动批量生成图片
- ListView usage in ERP-DEV
- [Web] What Is JSONP?
- Entity FrameWork 指导文章
- ETC_百度百科
- Javascript多线程引擎(四)
- SVN官方版本下载地址
- Kafka集群安装部署、Kafka生产者、Kafka消费者
- Django框架之第二篇
- EgretPaper学习笔记一 (安装环境,新建项目)
- SQL逻辑查询语句执行顺序 需要重新整理
- 学JS的心路历程-函式(六)其余参数及预设参数
- xampp 80端口被占用后这么办??解决了
- noip 提高组 2010
- C#实现ATM自动取款机
- 20172330 2017-2018-1 《Java程序设计》第七周学习总结
- Codeforces Round #169 (Div. 2) A水 B C区间更新 D 思路
热门文章
- iOS开发之让你的应用“动”起来
- CCS v5 无法启动解决办法及Launchpad仿真器电脑无法识别解决方法
- C++菱形继承的构造函数
- 利用jquery来隐藏input type=";file";
- NFinal 视图—用户控件
- java学习——abstract 和 final
- [canvas]通过动态生成像素点做绚丽效果
- 对list代理扩展功能
- Python3.5入门学习记录-File
- (原)ubuntu16在torch中使用caffe训练好的模型