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

上一篇:带你入门 Docker


下一篇:[js高手之路]Node.js+jade+express+mongodb+mongoose+promise实现todolist