poj2631 树的直径

设s-t是这棵树的直径,那么对于任意给予的一点,它能够到达的最远的点是s或者t。

这样我们可以通过2次bfs找到树的直径了。

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = ;
struct node
{
int to;
int v;
int next;
}edge[MAXN*];
int p,len;
int num[MAXN];
int vis[MAXN],pre[MAXN],ind,n;
void add(int x,int y,int z)
{
edge[ind].to = y;
edge[ind].v = z;
edge[ind].next = pre[x];
pre[x] = ind ++;
}
void bfs(int s)
{
int i;
queue<int>q;
vis[s] = ;
memset(num,,sizeof(num));
q.push(s);
while(!q.empty())
{
int temp = q.front();
q.pop();
for(i=pre[temp]; i!=-; i=edge[i].next){
int t = edge[i].to;
if(!vis[t]){
num[t] = num[temp] + edge[i].v;
//cout<<num[t]<<endl;
if(num[t] > len){
len = num[t];
p = t;
}
vis[t] = ;
q.push(t);
}
}
}
}
int main()
{
//freopen("data.txt","r",stdin);
int i,j;
ind = ;
memset(pre,-,sizeof(pre));
int x,y,z;
while(~scanf("%d%d%d",&x,&y,&z))
{
add(x,y,z);
add(y,x,z);
}
memset(vis,,sizeof(vis));
len = ;
bfs();
//cout<<p<<endl;
memset(vis,,sizeof(vis));
len = ;
bfs(p);
cout<<len<<endl;
return ;
}
上一篇:借助无线路由器+2台笔记本+Windows桥接功能,成功绕过了微信聊天记录迁移的BUG


下一篇:Oracle PLSql配置