首页 > 代码库 > 树的直径 poj 2631
树的直径 poj 2631
树的直径:从任意一点出发,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; }
树的直径 poj 2631
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。