求"到其他所有城市最远距离"最小的城市,并列时取编号最小。
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)。
请输出建设难度最小的城市编号;若有多个满足条件的城市,输出其中编号最小的那个。
无权图最短路BFS偏心率图的中心并列取最小
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、m;随后 m 行每行一条边的两个端点 uᵢ、vᵢ |
| 输出 | 建设难度最小的城市编号(并列取最小) |
| 数据范围 | 1 ≤ n ≤ 2000,1 ≤ m ≤ 2000 |
| 图的性质 | 无向图,且题面明确任意城市互相可达(连通) |
| 边的权值 | 全部视为 1(连通度数的是"道路条数") |
| 40% 的部分分 | 1 ≤ n ≤ 300 |
d(u, v) 数的是"经过的道路条数",不是路程长度,所以这是一张无权图输入:3 3,边为 1-2、1-3、2-3。三座城市围成一个三角形,任意两城之间都只隔一条路。
| 起点 u | d(u,1) | d(u,2) | d(u,3) | 难度 = 最大值 |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 |
| 2 | 1 | 0 | 1 | 1 |
| 3 | 1 | 1 | 0 | 1 |
三城难度都是 1,并列 → 取编号最小者 1 ✓
第 0 层:{1}
第 1 层:{2, 3}(都是 1 的邻居)
距离:d(1,1) = 0,d(1,2) = 1,d(1,3) = 1
最远距离 = 1
✅ 难度(1) = 1
难度(1) = 1
难度(2) = 1
难度(3) = 1
三者并列,输出最小城市编号
✅ 输出 1
输入:4 4,边为 1-2、2-3、3-4、2-4。城市 2 和城市 4 是整张图的"枢纽"。
| 起点 u | d(u,1) | d(u,2) | d(u,3) | d(u,4) | 难度 = 最大值 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 2 | 2 | 2 |
| 2 | 1 | 0 | 1 | 1 | 1 ← 最小 |
| 3 | 2 | 1 | 0 | 1 | 2 |
| 4 | 2 | 1 | 1 | 0 | 2 |
最小难度为 1(只有城市 2)→ 答案 2 ✓
第 0 层:{1}
第 1 层:{2}(1 只连 2)
第 2 层:{3, 4}(2 的邻居)
最远距离 = 2 → 难度(1) = 2
✅ 难度(1) = 2
第 0 层:{2}
第 1 层:{1, 3, 4}(全是 2 的邻居)
d(2,1) = d(2,3) = d(2,4) = 1
最远距离 = 1 → 难度(2) = 1
✅ 难度(2) = 1
难度:1 号 = 2、2 号 = 1、3 号 = 2、4 号 = 2
最小的是 1,只有城市 2 达到
所以不需要并列比较,直接输出 2
✅ 输出 2
对 n 个起点各做一次 BFS,取最远距离的最小值
三重循环直接算出所有点对距离,再逐行取最大值
| 方案 | 复杂度 | n = 2000 时的运算量 |
|---|---|---|
| n 次 BFS | O(n(n + m)) | ≈ 8 × 10⁶ ✅ |
| Floyd | O(n³) | ≈ 8 × 10⁹ ❌ 超时 |
| 顺带一提:两次 BFS 求直径 | O(n + m) | 只能求"最远点对",求不出每个点的偏心率 |
第一行输入 n 和 m,随后 m 行每行一条边的两个端点。程序会对每座城市做一次 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; }
v 第一次被访问到,它必然是由"离起点最近的那一层"扩展出来的,此时记下的层数就是最短距离,之后再也不会被更新。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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 了一条边,变成"有向图"后距离会算错。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 3 | 1 | 题面样例 1:三角形,三城并列难度 1 |
4 4 | 2 | 题面样例 2:城市 2 是枢纽,难度 1 |
4 3 | 2 | 一条链:难度 3, 2, 2, 3,2 和 3 并列 → 取 2 |
5 4 | 3 | 奇数长度链:正中间的城市 3 是唯一中心 |
4 3 | 1 | 菊花图:中心城市 1 难度为 1 |
1 1 | 1 | 只有一座城市的边界:唯一答案 1 |
ecc < bestEcc;写成 <= 会取到最大编号。distArr 必须在每次 BFS 前重置,否则上一轮结果会串进来。邻接表 O(n + m);每次 BFS 的 distArr 数组与队列各 O(n),可以复用同一份空间。
✅ 约 800 万次操作,1 秒内轻松跑完。而 Floyd 的 8 × 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 开始枚举 + 严格小于才更新 | 任何"最小值并列取小编号"的输出要求 |