(树的直径)给定一颗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;


}

选择题