[普及/提高-]A105548.城市规划

本题实在是没什么好讲的，算是某个形式上的模拟，所以简单略过。

题意（形式化）

给定一个无向图，对于 $\text{f}(i)$ 表示从顶点 $i$ 出发到任意点的最短路的最大值。找到一个数 $x$ 使 $\text{f}(x)$ 最小，若有多个可能的 $x$，则选取编号最小的。

思路

注意到 $n \le 2000$，于是可以暴力枚举，枚举每个顶点 $i$，从它为起点用 BFS 跑一遍最短路，并求出图中最大值。时间复杂度 $O(n^2)$ 时间充裕。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 2005 , M = 4005;
struct EDGE{
	int to , next;
}edge[M];
int dis[N] , head[N] , n , m , cnt , ans , maxn , minn = 0x3f3f3f3f;
bool vis[N];
void Add(int u , int v){
	edge[++ cnt] = {v , head[u]};
	head[u] = cnt;
	edge[++ cnt] = {u , head[v]};
	head[v] = cnt;
} 
queue<int> q;
void bfs(int s){
	memset(vis , 0 , sizeof(vis));
	q.push(s);
	vis[s] = 1;
	dis[s] = 0;
	while(!q.empty()){
		int t = q.front();
		q.pop();
		for(int i = head[t];~ i;i = edge[i].next){
			if(vis[edge[i].to] != 1){
				dis[edge[i].to] = dis[t] + 1;
				vis[edge[i].to] = 1;
				q.push(edge[i].to);
			}
		}
	}
}
signed main(){
	memset(head , -1 , sizeof(head));
	cin >> n >> m;
	for(int i = 1;i <= m;i ++){
		int u , v;
		cin >> u >> v;
		Add(u , v); 
	}
	for(int i = 1;i <= n;i ++){
		bfs(i);
		maxn = 0;
		for(int j = 1;j <= n;j ++){
			maxn = max(maxn , dis[j]);
			
		}
		if(minn > maxn){
			ans = i;
			minn = maxn;
		}
	}
	cout << ans << endl;
	return 0;
}