2025年12月GESP真题及题解(C++七级): 城市规划

2025年12月GESP真题及题解(C++七级): 城市规划

题目描述

A 国有n nn座城市，城市之间由m mm条双向道路连接，任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号。第i ii（1 ≤ i ≤ m 1\le i\le m1≤i≤m）条双向道路连接城市u i u_iui​与城市v i v_ivi​。

对于城市u uu和城市v vv而言，它们之间的连通度d ( u , v ) d(u,v)d(u,v)定义为从城市u uu出发到达城市v vv所需经过的双向道路的最少条数。由于道路是双向的，可以知道连通度满足d ( u , v ) = d ( v , u ) d(u,v)=d(v,u)d(u,v)=d(v,u)，特殊地有d ( u , u ) = 0 d(u,u)=0d(u,u)=0。

现在 A 国正在规划城市建设方案。城市u uu的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市，如果有多个满足条件的城市，则选取其中编号最小的城市。形式化地，你需要求出使得max ⁡ 1 ≤ i ≤ n d ( u , i ) \max\limits_{1\le i\le n}d(u,i)1≤i≤nmax​d(u,i)最小的u uu，若存在多个可能的u uu则选取其中最小的。

输入格式

第一行，两个正整数n , m n,mn,m，表示 A 国的城市数量与双向道路数量。

接下来m mm行，每行两个整数u i , v i u_i,v_iui​,vi​，表示一条连接城市u i u_iui​与城市v i v_ivi​的双向道路。

输出格式

输出一行，一个整数，表示建设难度最小的城市编号。如果有多个满足条件的城市，则选取其中编号最小的城市。

输入输出样例 1

输入 1

3 3 1 2 1 3 2 3

输出 1

1

输入输出样例 2

输入 2

4 4 1 2 2 3 3 4 2 4

输出 2

2

说明/提示

对于40 % 40\%40%的测试点，保证1 ≤ n ≤ 300 1\le n\le 3001≤n≤300。

对于所有测试点，保证1 ≤ n ≤ 2000 1\le n\le 20001≤n≤2000，1 ≤ m ≤ 2000 1\le m\le 20001≤m≤2000，1 ≤ u i , v i ≤ n 1\le u_i,v_i\le n1≤ui​,vi​≤n。

思路分析

这个问题实际上是在求图的中心点（center of a graph）：

• 对于每个节点，计算它到所有其他节点的最短距离中的最大值（这称为该节点的离心率/eccentricity）
• 找出离心率最小的节点，如果多个节点离心率相同，选择编号最小的

关键点：

1. 连通图保证：题目说明任意城市均可到达另一座城市，所以图是连通的
2. 边权为1：每条道路的长度视为1，所以连通度就是最短路径的边数
3. n ≤ 2000, m ≤ 2000：可以直接对每个节点做BFS求最短路径

算法选择：

• 对每个节点运行BFS，计算它到所有其他节点的距离
• 记录每个节点的最大距离（离心率）
• 比较所有节点的离心率，找到最小值对应的最小节点编号

时间复杂度：O(n(n+m)) = O(n² + nm)，在n=2000, m=2000时最多约8×10⁶次操作，可以接受

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=2005;// 最大城市数constintINF=1e9;// 无穷大值vector<int>g[N];// 邻接表存储图intn,m;// 城市数，道路数// 从起点s开始BFS，返回从s到所有节点的最短距离vector<int>bfs(ints){vector<int>dist(n+1,-1);// 距离数组，初始化为-1表示未访问queue<int>q;dist[s]=0;// 起点距离为0q.push(s);while(!q.empty()){intu=q.front();q.pop();// 遍历所有邻接节点for(intv:g[u]){if(dist[v]==-1){// 如果节点v未访问过dist[v]=dist[u]+1;// 更新距离q.push(v);// 加入队列}}}returndist;}intmain(){// 输入数据cin>>n>>m;// 读取m条边，构建无向图for(inti=0;i<m;i++){intu,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);// 无向图，双向添加}intmin_eccentricity=INF;// 最小离心率（建设难度）intbest_city=0;// 最佳城市编号// 对每个城市计算离心率for(inti=1;i<=n;i++){// 运行BFS获取从i到所有节点的距离vector<int>dist=bfs(i);// 计算离心率：从i到其他所有节点的最大距离inteccentricity=0;for(intj=1;j<=n;j++){eccentricity=max(eccentricity,dist[j]);}// 更新最优城市if(eccentricity<min_eccentricity){min_eccentricity=eccentricity;best_city=i;}// 如果离心率相同，选择编号更小的elseif(eccentricity==min_eccentricity&&i<best_city){best_city=i;}}// 输出结果cout<<best_city<<endl;return0;}

代码解释

数据结构

• vector<int> g[N]：邻接表存储图，g[u]存储与城市u直接相连的所有城市
• vector<int> dist：BFS中的距离数组，dist[i]表示从起点到城市i的最短距离

BFS函数

• 参数：起点s
• 功能：使用BFS计算从s到所有节点的最短距离
• 返回值：距离数组，dist[i]为从s到i的最短距离

主函数逻辑

1. 输入处理：读取n,m，构建无向图的邻接表
2. 离心率计算：对每个城市i：
   • 调用BFS(i)获取从i出发的最短距离
   • 找出所有距离中的最大值，即离心率
3. 最优选择：
   • 如果离心率比当前最小值小，更新最小值和最佳城市
   • 如果离心率相等但编号更小，更新最佳城市
4. 输出结果：打印最佳城市编号

功能分析

1. 正确性保证

• BFS保证计算的是最短路径（因为边权为1）
• 遍历所有节点计算离心率，不会遗漏
• 比较逻辑正确处理了多个最优解的情况

2. 时间复杂度

• 每个节点执行一次BFS：O(n+m)
• 总复杂度：O(n(n+m)) = O(n²+nm)
• 最坏情况：n=2000, m=2000，约8×10⁶次操作，完全可行

3. 空间复杂度

• 邻接表：O(n+m)
• BFS队列和距离数组：O(n)
• 总空间：O(n+m) ≤ O(4000)，非常高效

4. 边界情况处理

• 图连通：题目保证，不需要额外检查
• 自环和重边：不影响BFS正确性
• 多个最优解：比较逻辑确保选择编号最小的

示例验证

示例1

3 3 1 2 1 3 2 3

这是一个完全图（三角形）：

• 城市1：到2距离1，到3距离1 → 离心率=1
• 城市2：到1距离1，到3距离1 → 离心率=1
• 城市3：到1距离1，到2距离1 → 离心率=1
  离心率相同，选择编号最小的1

示例2

4 4 1 2 2 3 3 4 2 4

图结构：1-2-3-4，且2-4相连

• 城市1：到2(1), 3(2), 4(2) → 离心率=2
• 城市2：到1(1), 3(1), 4(1) → 离心率=1 ← 最小
• 城市3：到1(2), 2(1), 4(1) → 离心率=2
• 城市4：到1(2), 2(1), 3(1) → 离心率=2
  选择城市2

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}