树的直径 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;
}






 
相关文章
|
6月前
leetcode-543:二叉树的直径
leetcode-543:二叉树的直径
36 0
|
6月前
|
NoSQL 容器 消息中间件
树的直径、最近公共祖先、树的变形
树的直径、最近公共祖先、树的变形
|
6月前
|
算法 程序员
【算法训练-二叉树 三】【最大深度与直径】求二叉树的最大深度、求二叉树的直径
【算法训练-二叉树 三】【最大深度与直径】求二叉树的最大深度、求二叉树的直径
66 0
【Leetcode -404.左子叶之和 -543.二叉树的直径】
【Leetcode -404.左子叶之和 -543.二叉树的直径】
55 0
leetcode 543:二叉树的直径
leetcode 543:二叉树的直径
53 0
|
算法
图解LeetCode——543. 二叉树的直径
图解LeetCode——543. 二叉树的直径
10832 1
Leecode543. 二叉树的直径
Leecode543. 二叉树的直径
37 0
|
机器学习/深度学习
51nod 1405 树的距离之和 (树形dp)
51nod 1405 树的距离之和 (树形dp)
95 0
LeetCode 543. 二叉树的直径
LeetCode 543. 二叉树的直径
94 0
LeetCode 543. 二叉树的直径