树的直径:从随意一点出发,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;
}

最新文章

  1. Codeforces Round #341 Div.2 D. Rat Kwesh and Cheese
  2. OA项目笔记-从建立接口 dao impl action jsp等框架实现crud
  3. 简单几何(线段相交) POJ 1410 Intersection
  4. java 调用grads 自动批量生成图片
  5. ListView usage in ERP-DEV
  6. [Web] What Is JSONP?
  7. Entity FrameWork 指导文章
  8. ETC_百度百科
  9. Javascript多线程引擎(四)
  10. SVN官方版本下载地址
  11. Kafka集群安装部署、Kafka生产者、Kafka消费者
  12. Django框架之第二篇
  13. EgretPaper学习笔记一 (安装环境,新建项目)
  14. SQL逻辑查询语句执行顺序 需要重新整理
  15. 学JS的心路历程-函式(六)其余参数及预设参数
  16. xampp 80端口被占用后这么办??解决了
  17. noip 提高组 2010
  18. C#实现ATM自动取款机
  19. 20172330 2017-2018-1 《Java程序设计》第七周学习总结
  20. Codeforces Round #169 (Div. 2) A水 B C区间更新 D 思路

热门文章

  1. iOS开发之让你的应用“动”起来
  2. CCS v5 无法启动解决办法及Launchpad仿真器电脑无法识别解决方法
  3. C++菱形继承的构造函数
  4. 利用jquery来隐藏input type=&quot;file&quot;
  5. NFinal 视图—用户控件
  6. java学习——abstract 和 final
  7. [canvas]通过动态生成像素点做绚丽效果
  8. 对list代理扩展功能
  9. Python3.5入门学习记录-File
  10. (原)ubuntu16在torch中使用caffe训练好的模型