POJ2631 树的直径

发表于
字数统计: 672字 | 阅读时长 ≈ 2分钟

题目：POJ2631

题意： 大致就是村庄之间修路，从一个村庄到另一个村庄只有一条路，而不经过其他一些村庄两次。有若干村庄和道路，其中任何村庄都可以通过公路从任何其他村庄到达。就是让找出该地区两个最偏远村庄之间的公路距离。这些村庄从1开始编号。

题解： 这个就是求树的直径的模板题，两遍BFS即可，第一遍，从任意一个点遍历，记录最远的那个村庄，然后第二遍从第一遍找到的那个最远村庄为起点进行遍历，这样得到的就是两个最偏远地区的距离，即树的直径，本来想用邻接矩阵(浪费空间)存图，题目提到有多达1万条路，所以我选择了邻接表存数据。如果是初学者话，估计这个邻接表不太好理解，我尽可能用通俗的语言让大家理解

AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
struct {
	int u,v,w,next;//u,v是两个村庄；w是u,v两个村庄的距离;next 是记录此条路上一次存表的编号
}edge[10001];
int vis[10001]；//vis是遍历时记录该条路是否被访问
int d[10001]；//d是记录最远距离，遍历过程中不断更新
int head[10001];//head是记录每条路的头结点
int cnt,j,ans;
void add(int u,int v,int w)//邻接表的创建
{
    edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];//next指向上一次该路存表的编号，
	head[u]=cnt++;//将该条路的编号赋值给head
	
	}
void bfs(int x)
{
	memset(d,0,sizeof(d));
	memset(vis,0,sizeof(vis));
	vis[x]=1;
	queue<int>que;
	que.push(x);
	while(!que.empty())
	{
		int xx=que.front();
		que.pop();
		for(int i=head[xx];i!=-1;i=edge[i].next)//遍历与xx相连的所有村庄，i=-1即与xx相连的村庄遍历完了
		{
			int vv=edge[i].v;
			if(!vis[vv]&&d[vv]<d[xx]+edge[i].w)//不断维护最远距离
			{
				vis[vv]=1;
				d[vv]=d[xx]+edge[i].w;
				if(d[vv]>ans)
				{
					ans=d[vv];//ans是记录最远距离
					j=vv;//j是记录最偏远的村庄编号
				}
				que.push(vv);
			}
		}
	}
}
int main()
{
	int u,v,w;
		memset(head,-1,sizeof(head));
	while(~scanf("%d%d%d",&u,&v,&w))
	{
		add(u,v,w);add(v,u,w);//因为路是双向的，这也是可以用两遍BFS的原因
	}
	ans=0,cnt=0;
	bfs(1);
	bfs(j);//j是第一遍BFS找到的最远村庄的编号
	printf("%d\n",ans);
	return 0;
}
hey!baby,站住，点它!