3.无根树(tree)

题目描述

味味最近对树很感兴趣，什么是树呢？树就是有n个点和n-1条边形成的无环连通无向图。
今年2012年浙江省队选拔赛中味味发现了一个树中最长链(就是树当中距离最远的点对)试题，于是她着手对树进行了一些研究和思考。
味味在研究过程中想知道，对于一个无根树，当节点i作为根的时候树的高是多少。所谓树高指的是从根节点出发，到离根节点最远叶子节点所经过的节点的总数,详见输入输出样例1。
味味现在遇到了一些烦心的事情，不想再继续思考了，请你帮助她解决这个问题。

输入

输入文件名为 tree.in，共 N 行。第一行为一个正整数 N，表示树的节点个数。第2 行到第 N行里，每行两个用空格隔开的正整数a 和b，表示a 与b有连边。

输出

输出文件 tree.out 共N 行，第i行表示以节点i为根时的树高。

样例输入

【样例输入1】
3
1 2
2 3

【样例输入2】
4
1 4
2 4
3 4

样例输出

【样例输出1】
3
2
3

【样例输出2】
3
3
3
2

数据范围限制

对于30%的数据有 N≤ 100。
对于 60%的数据有 N≤ 300。
对于 100%的数据有 1≤N≤1000，1≤a，b≤N

提示

正解
我们可以用spfa，将两个相连的边的权值赋为1。然后spfa每个点，最后，每个点到离自己最远的那个点的距离+1就是答案。
AC代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,x1,y1,m,tot,head,tail,d[1005],v[1005],hd[1005],p[1005];
struct stu
{
   
	int w,to,next;
}a[2005];
void add(int x,int y,int z)//邻接表
{
   
	tot++;
	a[tot].w=z;
	a[tot].to=y;
	a[tot].next=hd[x];
	hd[x]=tot;
}
void spfa(int x)//spfa模板
{
   
	for(int i=1;i<=n;i++)d[i]=2147483647,v[i]=0;
	d[x]=0;v[x]=1;
	head=0;tail=1;
	p[tail]=x;
	while(head<tail)
	{
   
		head++;
		int y=p[head];
		for(int i=hd[y];i;i=a[i].next)
		 if(d[y]+a[i].w<d[a[i].to])
		 {
   
		 	d[a[i].to]=d[y]+a[i].w;
		 	if(v[a[i].to]==0)
		 	{
   
		 		p[++tail]=a[i].to;
				v[a[i].to]=1; 	
			}
		 }
		v[y]=0;
	}
}
int main()
{
   
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n-1;i++) 
	{
   
		cin>>x1>>y1;
		add(x1,y1,1);//连边（无向）
		add(y1,x1,1);
	}
	for(int i=1;i<=n;i++)//每个点跑一遍spfa
	{
   
		m=0;
		spfa(i);
		for(int j=1;j<=n;j++)//找离自己最远的点的最短距离
		 m=max(m,d[j]);
		cout<<m+1<<endl; //加1（自己的深度是1）
	}
	return 0;
}

下面附本次比赛的其它题目

2020.02.29模拟赛11（第一题）
2020.02.29模拟赛11（第二题）
2020.02.29模拟赛11（第三题）
2020.02.29模拟赛11（第四题）
2020.02.29模拟赛11（第五题）
2020.02.29模拟赛11（总结）

谢谢观看