Notice: Undefined index: name in /usr/www/lib/views/home/viewtitle.html on line 188
-完善程序 第 20 题
(树的直径)给定一颗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 题 ⑤处应填( )

解答部分以后会开放。