自动搬运

查看原文

来自洛谷，原作者为

	Computer1828 我已看不懂我的题解，如题解有误，我也不知道如何修改了，见谅。

搬运于2025-08-24 21:34:54，当前版本为作者最后更新于2020-02-13 12:50:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们机房的一位大佬曾经说过：

拿到一道题，要先把它简化了再做。

正文：

题目的大意：

在一个无向连通图中，求任意两点的最短路的最大值，答案乘上100后输出。

注意：有多组数据，当 $n$ 和 $m$ 都为 0 时结束程序

思路：

1、安息的 SPFA算法：

我自己就让我的程序TLE了，我还要交到评测姬上吗？

对于每一个图，遍历每个点，以这个点为起点做一次SPFA，得到以这个点为起点的最短路的最大值。最后把这些最大值取max，乘上100输出。

最优的时间复杂度：$O(T*(n+m))$

最坏的时间复杂度：$O(T*nm)$

2、Dijkstra算法：60分

因为在这个无向图中，每条边的边权都为1，所以我们可以用Dijkstra。

对于每一个图，遍历每个点，以这个点为起点做一次Dijkstra，得到以这个点为起点的最短路的最大值。最后把这些最大值取max，乘上100输出。（直接复制粘贴上面的）

时间复杂度：$O(T*nmlog_2 m)$

3、貌似很暴力的bfs：100分

按照SPFA的思路，遍历每个点，以这个点为起点进行bfs。

那么，为什么bfs是正确的：

因为每条边的边权都是1，所以我们不用像求最短路一样要做松弛操作。这也意味着，我们在bfs的时候，每个点被第一次搜到时与起点的距离就是最短的，所以我们不用像Dijkstra一样要用个优先队列一样找到最小的边并进行松弛操作。

又$\because$ 这是一个图。

$\therefore$ 所以我们遍历一次图只要$O(n)$的复杂度。

$\therefore$ 在遍历的时候，我们可以记录这个起点到每一个点的距离，记录的时候就可以顺便取max

时间复杂度：$O(T*nm)$

到此，我们直接写个图的bfs遍历不就行了？

我的100分代码：

#include<stdio.h>
#include<cstring>
#include<queue>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
int n,m;
struct edge{
	int to,nxt;
}e[50005];//使用链式前向星存图 
int hed[50005],cnt;//注意每组数据开始前要把hed和cnt数组清零 

inline void add(int u,int v){
	e[++cnt].to = v;
	e[cnt].nxt = hed[u];
	hed[u] = cnt;
}

bool vis[1005];//记得清零 

struct node{
	int tp,dis;//tp:当前点的编号;dis:从起点到这个点的距离 
};

int ans = -1;//最终的答案 
inline void bfs(int s){
	queue<node> q;
	q.push((node){s,0});//初始状态 
	vis[s] = true; 
	while(!q.empty()){
		node fr = q.front();
		q.pop();
		int u = fr.tp,dis = fr.dis;
		ans = max(ans,dis);//在遍历每个点的时候更新答案 
		for(int i = hed[u];i;i = e[i].nxt){
			int v = e[i].to;
			if(vis[v]) continue;
			q.push((node){v,dis+1});
			vis[v] = true;
		}
	}
}
int main(){
	while(true){
		scanf("%d%d",&n,&m);
		if(n==0 && m==0) break;
		ans = -1;//清零 
		memset(hed,0,sizeof(hed));
		cnt = 0;
		int u,v;
		for(register int i = 1;i<=m;++i){
			scanf("%d%d",&u,&v);
			add(u,v),add(v,u);//加双向边 
		}
		for(register int i = 1;i<=n;++i){//以i为起点进行bfs 
			memset(vis,false,sizeof(vis));//每次bfs开始前进行清零 
			bfs(i);
		}
		printf("%d\n",ans*100);
	}
	return 0;
}