不是VIP会员,不能显示答案

题目解答

题目:
(树的直径)给定一颗n个节点的树,每条边有个长度wi,求这棵树直径的长度。树的直径是指树的最长简单路。

做法:两次BFS。开始任选一点u作为起点进行BFS,找到最远的一点s,再从s再次BFS找到最远的一点t。s-t两点的路径长度就是直径的长度。

# include <iostream>

# include <cstring>

using namespace std;

const int inf= 0x3f3f3f3f; //假设的无穷大值,具体数值为1061109567

const int maxn=1005;

struct Node{

int to,w,next; //临接表节点,to表示这条边的终点,w表示这条边的长度,next表示下一条边的编号

} edge[maxn*2];

int head[maxn],tot; //head[u]表示u的临接表头节点的标号

int n; //节点树

int dis[maxn]; //离起点的距离

bool vis[maxn]; //某个点是否已经拜访过

int que[maxn],first,last; //队列

void init()

{

memset(head,-1,sizeof(head));

tot=0;

}

void addedge(int u,int v,int w)

{

edge[tot].to=v;

edge[tot].w= w;

edge[tot].next=head[u];

head[u]=tot++;

}

int BFS(int u)

{

first=last=0;

memset(dis,inf,sizeof(dis));

memset(vis,0, sizeof(vis));

dis[u]=0;

vis[u]=1;

que[last++]=u;

while(___(1)___)

{

u=que[first++];

for(int i=head[u]; i!=-1; i=edge[i].next)

{

int v=dege[i].to;

if(___(2)___)

{

vis[v]=1;

que[last++];

___(3)___;

}

}

}

int tmp=1;

for(int i=2; i<=n; i++)

if(___(4)___) tmp=i;

return tmp;

}

int main()

{

int u,v,w,s,t;

cin>>n;

init();

for(int i=1; i<n; i++)

{

cin>>u>>v>>w;

addedge(u,v,w);

addedge(v,u,w);

}

s=BFS(1);

___(5)___;

cout<< dis[t] << endl;

return 0;

}




选择题

1) ①处应填( )

2) ②处应填( )

3) ③处应填( )

4) ④处应填( )

5) ⑤处应填( )
考点:
分析:
解答:
评论:
老师: