GESP 题解库 / 7 级题解 / [GESP202512 七级] 城市规划 · 第 4 / 24 题
GESP202512 七级 · P14921 · 中等

城市规划

求"到其他所有城市最远距离"最小的城市,并列时取编号最小。

📊
n, m ≤ 2000
数据规模
🧭
偏心率最小
图的"中心"
⚡
O(n(n + m))
时间复杂度
🎯
n 次 BFS
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

A 国有 n 座城市,城市之间由 m 条双向道路连接,并且任意一座城市都可以经过若干条道路到达另一座城市(图保证连通)。第 i 条道路连接城市 uᵢ 与城市 vᵢ。

连通度 d(u, v) 定义为从城市 u 出发到达城市 v 所需经过的双向道路的最少条数。道路是双向的,所以 d(u, v) = d(v, u);特别地 d(u, u) = 0。

城市 u 的建设难度为它到其他城市的最大连通度,即 max d(u, i)(i 取遍 1 ~ n)。

请输出建设难度最小的城市编号;若有多个满足条件的城市,输出其中编号最小的那个。

💡
人话翻译:把每座城市都轮流当一次"起点",算出它到所有城市的最短距离,取其中最远的那个距离——这就是该城市的建设难度。
然后挑出建设难度最小的城市。
这个量在图论里叫"偏心率(eccentricity)",取到偏心率最小的点就是整张图的"中心"。

🔍 关键词提取

无权图最短路BFS偏心率图的中心并列取最小

已知条件

项目说明
输入第一行 n、m;随后 m 行每行一条边的两个端点 uᵢ、vᵢ
输出建设难度最小的城市编号(并列取最小)
数据范围1 ≤ n ≤ 2000,1 ≤ m ≤ 2000
图的性质无向图,且题面明确任意城市互相可达(连通)
边的权值全部视为 1(连通度数的是"道路条数")
40% 的部分分1 ≤ n ≤ 300

需要解决的问题

02
思维导图
整理解题思路的全貌
🧭 难度 = 到最远城市的距离(偏心率)
🧠 概念对齐
d(u,v):u 到 v 的最少边数
边权全部为 1 → 无权图
难度(u) = max d(u,i) = 偏心率
目标:让这个最大值最小
📐 算法设计
对每个起点 s 做一次 BFS
BFS 给出 s 到所有点的距离
取最大距离 = 城市 s 的难度
共 n 次,合计 O(n(n + m))
⚡ 规模估算
n, m ≤ 2000
一次 BFS 约 n + 2m ≈ 6000 步
总计约 2000 × 6000 = 1.2 × 10⁷
Floyd 要 8 × 10⁹,差三个数量级
⚠️ 易错点
并列时取了大编号(判断写成了 ≤)
用 Floyd 导致超时
BFS 前忘记把 dist 数组重置
反复建邻接表浪费常数
03
样例手算推导
两个样例的手算推演

🧮 样例 1:3 座城市两两相连(三角形),答案 1

输入:3 3,边为 1-2、1-3、2-3。三座城市围成一个三角形,任意两城之间都只隔一条路。

起点 ud(u,1)d(u,2)d(u,3)难度 = 最大值
10111
21011
31101

三城难度都是 1,并列 → 取编号最小者 1 ✓

1
从城市 1 出发 BFS

第 0 层:{1}

第 1 层:{2, 3}(都是 1 的邻居)

距离:d(1,1) = 0,d(1,2) = 1,d(1,3) = 1

最远距离 = 1

✅ 难度(1) = 1

2
比较三次结果

难度(1) = 1

难度(2) = 1

难度(3) = 1

三者并列,输出最小城市编号

✅ 输出 1

🔑
注意 d(u,u) = 0 不会干扰答案:我们要的是最大值,而 0 是数组里最小的那个,所以即使把 d(u,u) 一起拿去做 max,也不影响结果。只有当 n = 1 时,max 才会取到 0,此时难度为 0、答案就是城市 1。

🧮 样例 2:4 座城市 4 条路,答案 2

输入:4 4,边为 1-2、2-3、3-4、2-4。城市 2 和城市 4 是整张图的"枢纽"。

起点 ud(u,1)d(u,2)d(u,3)d(u,4)难度 = 最大值
101222
210111 ← 最小
321012
421102

最小难度为 1(只有城市 2)→ 答案 2 ✓

1
从城市 1 出发 BFS

第 0 层:{1}

第 1 层:{2}(1 只连 2)

第 2 层:{3, 4}(2 的邻居)

最远距离 = 2 → 难度(1) = 2

✅ 难度(1) = 2

2
从城市 2 出发 BFS

第 0 层:{2}

第 1 层:{1, 3, 4}(全是 2 的邻居)

d(2,1) = d(2,3) = d(2,4) = 1

最远距离 = 1 → 难度(2) = 1

✅ 难度(2) = 1

3
对比与取舍

难度:1 号 = 2、2 号 = 1、3 号 = 2、4 号 = 2

最小的是 1,只有城市 2 达到

所以不需要并列比较,直接输出 2

✅ 输出 2

⚠️
两个样例刚好覆盖了两种情形:样例 1 是并列(难度全为 1,所以要按编号取小);样例 2 是唯一最小(城市 2)。
做题时不要只盯着"最小值是多少",还要想清楚"并列时取哪个编号"——这正是本题最容易丢分的地方。
04
解法对比
n 次 BFS vs Floyd 全源最短路

⚔️ 解法对比

🟢 每个点做一次 BFS(推荐) 推荐

对 n 个起点各做一次 BFS,取最远距离的最小值

  • 时间 O(n(n + m))
  • n = m = 2000 时约 8 × 10⁶
  • 代码约 35 行
  • 空间 O(n + m)
💡
为什么 BFS 能求最短路?因为本题所有边的权都是 1,BFS 按"层"扩展,每个点第一次被访问时的层数就是它的最短路距离。这是无权图最短路的标准性质(权为 1 时也可用 Dijkstra,但没必要)。

🟠 Floyd 全源最短路

三重循环直接算出所有点对距离,再逐行取最大值

  • 时间 O(n³) = 8 × 10⁹
  • 本题限时 1 s
  • 必然超时
  • 只在 n ≤ 300 的部分分可行
⚠️
为什么 40% 的部分分推荐 Floyd?当 n ≤ 300 时,n³ = 2.7 × 10⁷,非常轻松,而且 Floyd 代码只有 5 行。但满分必须换成 n 次 BFS——这就是"部分分算法"与"满分算法"的典型分界。

📈 性能对比

方案复杂度n = 2000 时的运算量
n 次 BFSO(n(n + m))≈ 8 × 10⁶ ✅
FloydO(n³)≈ 8 × 10⁹ ❌ 超时
顺带一提:两次 BFS 求直径O(n + m)只能求"最远点对",求不出每个点的偏心率
05
算法流程图
逐点 BFS 求偏心率,取最小值
开始读入 n, m,建无向图邻接表best = +∞,ans = 1for u = 1 到 n:从 u 出发做一次 BFS,得到 dist[1..n]难度(u) = max{ dist[1], dist[2], …, dist[n] }难度(u) < best 吗?是 ✓best = 难度(u);ans = u否 ✗保持不动,编号自然取小u 还没枚举完吗?输出 ans枚举下一座城市
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧭 最小建设难度的城市

第一行输入 n 和 m,随后 m 行每行一条边的两个端点。程序会对每座城市做一次 BFS,并列出它的建设难度。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(逐点 BFS 求偏心率)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
vector<int> adj[MAXN];      // 邻接表
int distArr[MAXN];          // 单次 BFS 的距离数组

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);        // 双向道路,两边都要连
    }

    int bestEcc = INT_MAX, ans = 1;
    for (int s = 1; s <= n; s++) {          // 每座城市都当一次起点
        // ---- 一次 BFS:无权图单源最短路 ----
        for (int i = 1; i <= n; i++) distArr[i] = -1;
        queue<int> q;
        distArr[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (distArr[v] == -1) {         // 第一次到达即最短
                    distArr[v] = distArr[u] + 1;
                    q.push(v);
                }
            }
        }

        // ---- 该城市的建设难度 = 最远距离 ----
        int ecc = 0;
        for (int i = 1; i <= n; i++) ecc = max(ecc, distArr[i]);

        if (ecc < bestEcc) {                // 严格小于 → 并列时保留小编号
            bestEcc = ecc;
            ans = s;
        }
    }

    printf("%d\n", ans);
    return 0;
}
🔑
为什么"第一次到达就是最短路"?BFS 是一层一层往外扩展的:先把距离 0 的点(自己)入队,再是距离 1 的所有邻居,然后是距离 2 ……
所以当某个点 v 第一次被访问到,它必然是由"离起点最近的那一层"扩展出来的,此时记下的层数就是最短距离,之后再也不会被更新。
这个性质只对"边权全为 1"的图成立,一旦边权不同就得用 Dijkstra。

📖 关键几行怎么看

代码作用为什么这样写
adj[u].push_back(v); adj[v].push_back(u);建图道路是双向的,必须连两条
for (int s = 1; s <= n; s++)枚举起点每个城市都要算一次自己的偏心率
if (distArr[v] == -1) distArr[v] = distArr[u] + 1;BFS 求最短路无权图中"首次到达"即最短
ecc = max(ecc, distArr[i]);算偏心率取到所有城市的最远距离
if (ecc < bestEcc) { … ans = s; }更新答案严格小于:并列时保留小编号
⚠️
四个坑:① 判断写成 ecc <= bestEcc,于是 n 座城市逐一遍历时最后一个并列者会覆盖答案,编号最大而不是最小;② 用了 Floyd,n = 2000 时 8 × 10⁹ 直接超时;③ 每次 BFS 前忘记把 distArr 重置为 −1,上一轮的距离会污染下一轮;④ 建图时只 push_back 了一条边,变成"有向图"后距离会算错。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 3
1 2
1 3
2 3
1题面样例 1:三角形,三城并列难度 1
4 4
1 2
2 3
3 4
2 4
2题面样例 2:城市 2 是枢纽,难度 1
4 3
1 2
2 3
3 4
2一条链:难度 3, 2, 2, 3,2 和 3 并列 → 取 2
5 4
1 2
2 3
3 4
4 5
3奇数长度链:正中间的城市 3 是唯一中心
4 3
1 2
1 3
1 4
1菊花图:中心城市 1 难度为 1
1 1
1 1
1只有一座城市的边界:唯一答案 1
✅
自查清单:① 更新条件写的是严格小于吗?② 复杂度是 O(n(n + m)) 而不是 O(n³) 吗?③ 每次 BFS 前 dist 重置了吗?④ 无向边连了两条吗?

🚨 易错点清单

⚠️
并列取反:题面要求"多个城市时取编号最小",更新条件必须是 ecc < bestEcc;写成 <= 会取到最大编号。
⚠️
选错算法:n ≤ 2000 时 Floyd 需要 8 × 10⁹ 次运算,要用 n 次 BFS 才能稳过。
⚠️
距离数组未清空:distArr 必须在每次 BFS 前重置,否则上一轮结果会串进来。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n(n + m))
空间复杂度
O(n + m)
n, m 最大
2000
运算量
约 8 × 10⁶

时间怎么算的?

空间都用在哪?

邻接表 O(n + m);每次 BFS 的 distArr 数组与队列各 O(n),可以复用同一份空间。

✅ 约 800 万次操作,1 秒内轻松跑完。而 Floyd 的 8 × 10⁹ 大了三个数量级,这正是"部分分算法"与"满分算法"的分水岭。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// —— 无权图 BFS 求单源最短路模板 ——
queue<int> q;
dist[s] = 0;
q.push(s);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u])
        if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
}

// —— 本题核心:偏心率(eccentricity)——
// 难度(u) = max_i dist_i ;对所有 u 取最小值即"图的中心"
// 注意:只有"边权全为 1"时才能用 BFS,否则换 Dijkstra

// —— 若只要求"最远的一对点"(图的直径)——
// 随便找一个点做 BFS,得到最远点 a;
// 再从 a 做一次 BFS,得到的最远距离就是直径 → O(n + m)

// —— 若 n 更小(≤ 300)而要求所有点对距离 ——
// Floyd:for k / for i / for j  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
BFS 求单源最短路每个起点一次,层数即距离无权图最短路、迷宫最短路
取 max 求偏心率最远距离就是"难度"选址问题、图的中心/半径
按规模选算法n ≤ 300 用 Floyd,n ≤ 2000 用 n 次 BFS一切"复杂度与数据范围匹配"的题
并列取最小从 1 开始枚举 + 严格小于才更新任何"最小值并列取小编号"的输出要求
🌟
思考题:如果题目改成"求到其他城市最远距离不超过 k 的城市个数",算法要怎么改?(提示:完全不用改主体——照旧对每个城市做一次 BFS 求出偏心率,然后把偏心率 ≤ k 的城市全部输出即可。本题只问"最小的是哪个",但既然我们已经算出了每个城市的建设难度,改问别的统计口径几乎不需要额外代价。做题时顺手把中间量都存下来,往往能应付很多变式。)