城市规划 题解

题目分析

本题给定一张包含 $n$ 个节点、$m$ 条边的连通无向图。定义任意两城市 $u,v$ 之间的连通度 $d(u,v)$ 为它们之间的最短路径长度（经过的最少边数）。对于一座城市 $u$，它的建设难度定义为它到其他所有城市连通度的最大值，即：

在图论中，这个值也被称为顶点 $u$ 的偏心距。而我们要找的是偏心距最小的顶点（称为图的中心），如果有多个中心，输出编号最小的那个。

数据范围：$n \le 2000$，$m \le 2000$，图连通。这样的数据规模允许我们使用较为直接的方法。

解题思路

由于每条边的边权均为 $1$，计算单源最短路可以直接采用广度优先搜索（BFS）。BFS 从起点出发，按层扩展，能够保证第一次访问某个节点时的距离就是最短距离。

如果对每个城市都做一次 BFS，就可以得到该城市到所有其他城市的最短距离，进而得到它的偏心距。最后在所有偏心距中取最小值，若出现多个则保留编号较小的城市。

这一思路的流程如下：

1. 读入 $n,m$ 并建图（使用邻接表）。
2. 对于 $i$ 从 $1$ 到 $n$：
   • 以 $i$ 为起点进行 BFS，得到距离数组 $d$。
   • 在 BFS 过程中或结束后，找出距离的最大值，记为 $mx[i]$。
3. 遍历所有 $mx[i]$，找到最小值对应的最小下标。
4. 输出答案。

因为 $n$ 和 $m$ 最大只有 $2000$，进行 $n$ 次 BFS 的总复杂度约为 $O(n(n+m))$，在 $8 \times 10^6$ 级别，完全可以在 1s 时限内运行完毕。

算法说明

BFS 求偏心距

对于给定的起点 u，执行以下步骤：

• 初始化距离数组 d[1..n] 为一个极大值（例如 n+1），d[u] = 0。
• 将起点入队。使用队列（用数组模拟即可）。
• 当队列不为空时：
  • 取出队首元素 x。
  • 遍历 x 的所有邻接点 y，若 d[x] + 1 < d[y]，则更新 d[y] = d[x] + 1，并将 y 入队。
• BFS 结束后，队列中最后一个被弹出的节点（或最后入队的节点）的距离就是偏心距。这是因为 BFS 按层序访问，最后访问的节点一定离起点最远。

在参考代码中，采用了 mx[u] = d[q[qr]] 来记录偏心距，其中 qr 是队列的尾部指针，q[qr] 即最后一个入队的节点。

寻找答案

初始化 ans = 1，然后枚举 $i = 1 \dots n$，如果 mx[i] < mx[ans]，则更新 ans = i。因为我们是按编号从小到大检查，所以当偏心距相等时，不会更新，这样就自动保留了编号最小的城市。

时间复杂度分析

• BFS 单次：每个顶点和每条边均只会被访问常数次，时间复杂度 $O(n + m)$。
• 进行 $n$ 次 BFS：总时间复杂度 $O(n(n + m))$。
• 对于最大值 $n = 2000, m = 2000$，运算量约为 $2000 \times (2000 + 2000) = 8 \times 10^6$，非常轻松。
• 空间复杂度：邻接表存储 $O(n + m)$，距离数组等 $O(n)$，总体 $O(n + m)$。

参考代码

以下是基于 C++ 的参考代码，采用数组模拟队列以减少 STL 常数开销：

cpp
复制
1#include <cstdio>
2#include <algorithm>
3#include <vector>
4using namespace std;
5const int N = 2005;
6
7int n, m;
8vector<int> e[N];   // 邻接表
9int d[N], mx[N], q[N]; // d:临时距离, mx:偏心距, q:队列
10
11// 对城市 u 进行 BFS，计算偏心距
12void bfs(int u) {
13    // 初始化距离为极大值
14    for (int i = 1; i <= n; i++)
15        d[i] = n + 1;
16    d[u] = 0;
17    q[1] = u;
18    int ql = 1, qr = 1;  // 队头、队尾指针
19    while (ql <= qr) {
20        int x = q[ql++];
21        for (auto y : e[x]) {
22            if (d[x] + 1 < d[y]) {
23                d[y] = d[x] + 1;
24                q[++qr] = y;
25            }
26        }
27    }
28    // 最后一个入队的节点距离即为偏心距
29    mx[u] = d[q[qr]];
30}
31
32int main() {
33    scanf("%d%d", &n, &m);
34    for (int i = 1; i <= m; i++) {
35        int u, v;
36        scanf("%d%d", &u, &v);
37        e[u].emplace_back(v);  // 等价于 push_back
38        e[v].emplace_back(u);
39    }
40    int ans = 1;
41    for (int i = 1; i <= n; i++) {
42        bfs(i);
43        if (mx[i] < mx[ans])
44            ans = i;
45    }
46    printf("%d\n", ans);
47    return 0;
48}

代码要点说明

1. 邻接表建图：使用 vector<int> e[N]，便于遍历每个节点的邻居。
2. 数组模拟队列：q 存储节点，ql、qr 分别指向队首和队尾，比 STL queue 稍快。
3. 距离初始化：d[i] = n + 1 是一个绝对大于任何可能距离的值（图中最长距离不会超过 $n-1$）。
4. 偏心距记录：BFS 中 q[qr] 始终是当前最后入队的节点，其距离自然就是这一层的最远距离，也就是该起点的偏心距。
5. 答案更新：if (mx[i] < mx[ans]) 采用严格小于，保证相等偏心距时保留编号较小的城市。

总结

本题考查了图的中心概念以及 BFS 在无权图最短路中的应用。由于数据范围适中，直接对每个顶点做一次 BFS 即可在时限内解决问题。理解 BFS 的特性和队列中元素距离的单调性，能够帮助我们简洁地求出偏心距。此题也体现了“图的中心”这一经典问题在竞赛中的基本解法。