企业官网建设流程全解析

1. 题目长什么样：先把它讲清楚

1.1 请出本题的“回忆版”题面

在机考圈子里，只要看到“找城市”这三个字，很多老手都会会心一笑。这是一道典型的图论中心问题，分值给到200分，难度其实不低——不是因为它本身有多烧脑，而是因为它隐含了多种解法路径，不同数据范围对应完全不同的最优策略。你要是只会一种写法，遇上大数据直接超时；要是理解到位，写哪个版本都能拿高分。

我把常见题目形态整理成下面这个版本，后面所有实现都围绕它展开：

输入第一行是两个整数 n 和 m，表示一共有 n 个城市，编号从 1 到 n，m 条无向道路。接下来 m 行，每行给两个整数 u、v，表示城市 u 和 v 之间有一条直接连通的边。题目保证整个城市图是连通的，即任意两个城市都能通过若干条道路互相到达。

现在要在这 n 个城市里选一个城市作为“中心城市”。定义中心城市到其他所有城市的最短路径长度之和为它的得分。得分越小越好，如果有多个城市得分相同，输出编号最小的那个。输出格式就是一行两个整数：城市编号和得分。

举个例子，输进去 5 个城市，它们串成一条线 1-2-3-4-5，那么中心城市就是正中间的 3 号，得分为 3 到 1 的距离 2，加上 3 到 2 的距离 1，再加上 3 到 4 的距离 1，再加上 3 到 5 的距离 2，总共 6。如果你选 2 号城市，得分是 1+0+1+2+3=7，怎么都比 6 大，所以结果输出“3 6”。

1.2 用生活类比理解“最短路径和最小”

这道题的本质，是在一张无向无权图里找一个“最靠近所有人”的节点。你可以把它想象成几个朋友要选一家餐厅聚会，目标是让所有人到餐厅的路程加起来最短。城市图里的边就是道路，路长都是 1，最短路径就是最少经过几条边。

图论里管这个叫“1-中心点”问题，也有人叫它“图的中心性度量”。物流选址、CDN 节点部署、通信基站选址，背后都是同一套数学模型。所以这道题看起来只是在“找城市”，其实练的是最基础也最常用的图遍历技巧。

1.3 刷这道题能锻炼到什么

我说句实在话，这道题最妙的地方在于，它同时能考察 BFS、全源最短路径、树的动态规划三块内容。你用一个解法解决它不算厉害，能把三种解法都看明白，才算真正吃透。

适合看这篇文的人有三种：一是准备机考，需要 200 分题稳定拿全；二是面试前想快速梳理图的题感；三是做前端、后端、客户端的同学，想在 Java、JS、Python、C 之间切换时，顺便把语言差异和 I/O 习惯都熟练一遍。这也是我坚持把这四种语言都写一遍的原因，光看懂一个语言没有用，得多语言对照着看，底层思路才记得牢。

2. 算法选型：从暴力到最优的三套思路

2.1 方案一：每个城市 BFS 全算一遍

先聊最直白的做法。既然是求某个城市到其他所有城市的最短路径，那就用 BFS 从每个城市挨个跑一遍，把距离累加起来，记下最小值。BFS 在无权图里天然就是最短路径算法，因为它一层一层往外扩，第一次访问到的节点一定是最短距离。

每个起点跑一次 BFS，时间复杂度是 O(n + m)。要把 n 个城市都当一次起点，总复杂度就是 O(n * (n + m))。这个复杂度看着吓人，但在小数据下完全够用。比如 n=1000，m=2000，那么总操作也就是一千万量级，Java、C 都能轻松跑完，Python 稍微注意一下写法也能接受。

我建议初学者先把这段代码写对、写熟。它的优势就是简单、无脑、不容易出错，而且不依赖图是不是树这种特殊结构。任何连通图，哪怕是环套环，它都能算。

2.2 方案二：Floyd 兜底，适合稠密小图

很多人一看到“最短路径”三个字，第一个想到的是 Floyd-Warshall 算法。它用三重循环枚举中转点，能算出所有点对之间的最短路径，非常标准。

但 Floyd 的复杂度是 O(n³)，n 超过 200 就比较吃力，超过 500 基本就别想了。所以它只适合 n 很小、边又特别多的稠密图。比如 n=50，边数满打满算 1225 条，你用 Floyd 先算全部距离，再逐行求和，代码确实很简短。

在实际机考里，我一般不建议优先选 Floyd。原因有两个：第一，大部分题目给的是 n 到一万、m 到一万的稀疏图，O(n³) 完全不可行；第二，同样是全源最短路径，BFS 对无权图的效率要远高于 Floyd，没必要为了“写法经典”放弃性能。Floyd 更适合作为面试时的理论补充，而不是机考首选。

2.3 方案三：当图是一棵树时，换根 DP 一击制胜

这里要放大招。如果题面里的 m = n - 1，说明图其实是一棵树。树没有环，任意两个城市之间只有唯一一条简单路径。这种情况下，存在 O(n) 的解法，叫做“换根动态规划”。

思路不复杂。我们先随便选 1 号城市当根，做一次 DFS，统计两件事：一是每个节点的子树大小 sz[u]，即这个节点以下有多少个城市；二是 dp[u]，表示把 u 当根时，u 到它整个子树里所有节点的距离之和。

第一次 DFS 从上往下走，状态转移是：

dp[u] = sum(dp[v] + sz[v])，其中 v 是 u 的直接子节点

这个公式的含义是：u 到 v 子树里每个节点的距离，等于 v 到这些节点的距离再加上 u 到 v 这段边。每个节点都加一次，所以累加的是 dp[v] + sz[v]。

第二次 DFS 做换根。假设 u 是 v 的父节点，我们已经知道了 dp[u] 和 dp[v]（v 作为子树根），现在想求“如果把整棵树的根从 u 换到 v”，新的 dp[v] 是多少。

关键变化只有两条：原本在 v 子树里的那 sz[v] 个节点，距离 v 比距离 u 少 1；而其他 n - sz[v] 个节点，距离 v 比距离 u 多 1。所以：

dp[v] = dp[u] - sz[v] + (n - sz[v]) = dp[u] + n - 2 * sz[v]

这个公式推出来以后，整个题就变成了 O(n) 的两次 DFS。我当年第一次看懂这个推导时特别兴奋，因为这比暴力 BFS 快了不止一个数量级，而且代码量并不大。

2.4 如果有边权怎么办

上面的分析都建立在“每条道路长度是 1”这个前提上。但有些变体题目会给边权，比如一条路修得好走一点，长度标记为 5。这种情况下，BFS 就不再适用了，因为 BFS 按“层数”扩展，它默认所有边的代价相等，一旦边权不同，先访问到的路径不一定最短。

解决方案很简单，把单源最短路径从 BFS 换成 Dijkstra。每个城市当起点跑一遍 Dijkstra，复杂度变成 O(n * (m log n))。如果图特别小，也可以继续用 Floyd 一步到位。不管哪种方式，最终统计“每个城市到其他所有城市最短路径和”的逻辑都不变。

所以你看，核心思路永远是固定的：先算全源最短路径，再按行求和，最后找最小值和最小下标。变的只是“用什么算法算全源最短路径”而已。

3. 四种语言落地：从伪代码到 AC

3.1 Java 实现：一边写代码一边避开快读的坑

Java 在机考里最让人头疼的不是算法本身，而是输入输出。Scanner 用起来顺手，但性能差，当 n 上万、m 几万时，Scanner 硬生生会把读输入的时间拖成算法的好几倍。所以我习惯直接用 StreamTokenizer 或者干脆用 BufferedReader 按行读。下面的代码里我用 BufferedReader + split 处理，既简单又够快。

import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); List<Integer>[] g = new ArrayList[n + 1]; for (int i = 1; i <= n; i++) { g[i] = new ArrayList<>(); } for (int i = 0; i < m; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); g[u].add(v); g[v].add(u); } int bestCity = 0; long bestSum = Long.MAX_VALUE; for (int s = 1; s <= n; s++) { int[] dist = new int[n + 1]; Arrays.fill(dist, -1); Queue<Integer> queue = new LinkedList<>(); queue.offer(s); dist[s] = 0; long sum = 0; while (!queue.isEmpty()) { int u = queue.poll(); sum += dist[u]; for (int v : g[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; queue.offer(v); } } } if (sum < bestSum) { bestSum = sum; bestCity = s; } } System.out.println(bestCity + " " + bestSum); } }

两点提醒，第一，dist 数组初始化成 -1，这样既能当“是否访问过”的标记，又不会和真实距离 0 混淆。第二，累加结果 sum 我用了 long。你可能会觉得 n 只有一万，距离和撑死不超过一亿，int 够用；但万一平台把 n 提升到十万、二十万呢？用 long 不亏，属于零成本的稳妥。

3.2 JavaScript/Node.js 实现：readline 和队列的正确打开方式

用 JS 写机考题，首先要适应 Node.js 的 readline 异步读取方式。这个和 Java/Python 的同步读不一样，很多人第一次写容易踩坑：以为 input 数组已经读完了，其实 close 回调还没触发。标准写法是把所有行收进数组，在 close 事件里统一处理。

另外一个小细节，JS 的数组很适合当队列，但要避免用 shift() 来弹出队首，因为 shift 是 O(n) 的，会拖慢整体性能。正确做法是用一个 head 指针模拟队首位置，每出队一个元素就把 head 加一，等 head 追上数组长度再重置，这样出队操作也是 O(1)。

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); const lines = []; rl.on('line', (line) => lines.push(line)); rl.on('close', () => { const [n, m] = lines[0].split(' ').map(Number); const g = Array.from({ length: n + 1 }, () => []); for (let i = 1; i <= m; i++) { const [u, v] = lines[i].split(' ').map(Number); g[u].push(v); g[v].push(u); } let bestCity = 0; let bestSum = Infinity; for (let s = 1; s <= n; s++) { const dist = new Array(n + 1).fill(-1); const queue = [s]; let head = 0; dist[s] = 0; let sum = 0; while (head < queue.length) { const u = queue[head++]; sum += dist[u]; for (const v of g[u]) { if (dist[v] === -1) { dist[v] = dist[u] + 1; queue.push(v); } } } if (sum < bestSum) { bestSum = sum; bestCity = s; } } console.log(bestCity + ' ' + bestSum); });

如果你在 Windows 本地跑 JS，遇到 PowerShell 说“因为在此系统上禁止运行脚本”之类的话，那不是代码的问题，是执行策略限制。直接用 cmd 窗口运行 node main.js，或者用管理员权限打开 PowerShell 查一下脚本策略即可，不必为此纠结。

3.3 Python 实现：读完全量输入再处理

Python 的性能在于“少写慢操作”。不要在循环里频繁用 sys.stdin.readline()，更不要用 input() 逐行读取，最好的方式是 sys.stdin.buffer.read().split() 把整个输入一次性读进来，再转成迭代器。这样写出来的代码不仅短，速度也能提升好几倍。

BFS 部分我直接用 collections.deque。deque 的 popleft 是 O(1)，而 list 的 pop(0) 是 O(n)，数据一大会特别亏。

import sys from collections import deque def main(): data = sys.stdin.buffer.read().split() it = iter(data) n = int(next(it)) m = int(next(it)) g = [[] for _ in range(n + 1)] for _ in range(m): u = int(next(it)) v = int(next(it)) g[u].append(v) g[v].append(u) best_city = 0 best_sum = 10 ** 18 for s in range(1, n + 1): dist = [-1] * (n + 1) dist[s] = 0 q = deque([s]) total = 0 while q: u = q.popleft() total += dist[u] for v in g[u]: if dist[v] == -1: dist[v] = dist[u] + 1 q.append(v) if total < best_sum: best_sum = total best_city = s print(best_city, best_sum) if __name__ == "__main__": main()

这段代码已经可以在绝大多数机考环境里直接跑通。唯一要注意的是 Python 的递归深度问题，如果你换成 DFS 写法，记得补 sys.setrecursionlimit。BFS 没有递归，所以完全不受限制，这也是我偏好 BFS 的原因之一。

3.4 C 实现：把内存和队列控制在自己手里

写 C 版本最爽的地方，是你能清楚地看到每一块内存怎么分配、队列怎么移动。用结构体加数组实现邻接表，比指针链表更安全，也更容易调试。我把边的数组开成 2 倍，是因为每条无向边要存两次。

#include <stdio.h> #include <string.h> #define MAXN 10005 #define MAXM 200005 int head[MAXN], to[MAXM], nxt[MAXM], edgeCnt; int queue[MAXN], dist[MAXN]; void addEdge(int u, int v) { to[++edgeCnt] = v; nxt[edgeCnt] = head[u]; head[u] = edgeCnt; } int main() { int n, m; scanf("%d %d", &n, &m); memset(head, 0, sizeof(head)); memset(nxt, 0, sizeof(nxt)); edgeCnt = 0; for (int i = 0; i < m; i++) { int u, v; scanf("%d %d", &u, &v); addEdge(u, v); addEdge(v, u); } int bestCity = 0; long long bestSum = 0x3f3f3f3f3f3f3f3fLL; for (int s = 1; s <= n; s++) { memset(dist, -1, sizeof(int) * (n + 1)); int headIdx = 0, tailIdx = 0; queue[tailIdx++] = s; dist[s] = 0; long long sum = 0; while (headIdx < tailIdx) { int u = queue[headIdx++]; sum += dist[u]; for (int e = head[u]; e; e = nxt[e]) { int v = to[e]; if (dist[v] == -1) { dist[v] = dist[u] + 1; queue[tailIdx++] = v; } } } if (sum < bestSum) { bestSum = sum; bestCity = s; } } printf("%d %lld\n", bestCity, bestSum); return 0; }

C 的坑主要在于数组越界。MAXN 和 MAXM 一定要根据题目数据上限来开，并且在本地自测时故意造一条 n 到达上限的链式数据，确保队列能装下所有节点。另一个容易忽略的地方是 memset 的字节数，我习惯只重置用到的 0 到 n 这一块，避免每次循环都重置整个数组造成无畏浪费。

3.5 树的换根 DP 快速模板

如果你的题目明确给定 m = n - 1，或者你通过数据范围判断出这是一棵树，那我强烈建议直接用下面的 Python 换根 DP。它和 BFS 暴力解相比，代码长度差不多，但时间复杂度从 O(n²) 直接降到 O(n)。

import sys sys.setrecursionlimit(1 << 25) def main(): data = sys.stdin.buffer.read().split() it = iter(data) n = int(next(it)) m = int(next(it)) g = [[] for _ in range(n + 1)] for _ in range(m): u = int(next(it)) v = int(next(it)) g[u].append(v) g[v].append(u) sz = [0] * (n + 1) dp = [0] * (n + 1) def dfs1(u, fa): sz[u] = 1 for v in g[u]: if v == fa: continue dfs1(v, u) sz[u] += sz[v] dp[u] += dp[v] + sz[v] def dfs2(u, fa): for v in g[u]: if v == fa: continue dp[v] = dp[u] + n - 2 * sz[v] dfs2(v, u) dfs1(1, 0) dfs2(1, 0) best_city = min(range(1, n + 1), key=lambda x: (dp[x], x)) print(best_city, dp[best_city]) if __name__ == "__main__": main()

代码里的关键就三行：dfs1 算子树大小和根节点答案；dfs2 用换根公式传播答案；最后用 min 加 lambda 按“得分小优先、编号小次优先”的原则取出答案。lambda 里的 key 返回一个元组，Python 会先比较第一个值，再比较第二个值，正好实现平局取编号最小的需求。这一手在竞赛里很常见，比写 if 判断清爽得多。

4. 避坑清单：这些细节决定 200 分还是 0 分

4.1 三个值得认真复盘的细节

第一，平局输出编号最小。很多人用 if (sum <= bestSum) 去更新答案，结果遇到两个城市得分相同时，会把编号大的覆盖掉编号小的，直接扣掉一个测试点。正确写法是 if (sum < bestSum)，这样第一次遇到编号小的城市就会一直保留。

第二，BFS 的初始距离到底是 0 还是 1。我见过不少同学把起点 dist[s] 设成 1，理由是“路径长度至少包含自己”。这是错的，起点到自己的距离就是 0，设成 1 会导致所有城市的距离和整体偏大，虽然城市编号可能不受影响，但输出得分就错了。

第三，连通性。题目保证了连通图，所以在我的代码里不需要处理不可达节点。但如果你在本地测试时自己造了非连通数据，那么 dist 为 -1 的节点会直接把你搞蒙，因为它们既没有参与求和，也没有任何提示。稳妥一点的做法是先 BFS 一遍确认能访问到 n 个节点，再进入主循环。这个检查花不了多少时间，但能避免数据问题导致的连环失误。

4.2 自测用例参考

光会写代码不够，还得会自己验证。我贴三个最典型的用例，用来确定你的程序没写歪：

第三个用例特别值得跑，因为环上的对称性会让每个城市得分完全一样，如果你的更新条件是正确的小于号，输出会是 1；如果写成小于等于，有可能变成 4。用这个用例直接暴露平局处理问题。

4.3 数据规模与选型对照

我自己在本地做过一轮粗略测试，数据是随机树结构，边数等于 n - 1。不同 n 下两种方案的耗时差距非常大：

这里的耗时受语言影响也很大。C 和 Java 在 10000 节点时跑 BFS 都还能接受，Python 就明显吃力。所以别迷信“暴力能过”，要看你所用语言和数据上限。稳妥策略永远是：先写暴力保底，再写树 DP 优化，最后看数据规模决定提交哪个版本。

5. 最后分享一点实战心得

我个人做这类题的习惯是：拿到题面先看 n 和 m 的范围，再看边数是不是恰好 n - 1。如果边数等于节点数减一，我默认走换根 DP；如果是一般图，BFS 暴力兜底；如果 n 特别小但边权存在，再考虑 Floyd 或 Dijkstra。这个判断流程比背模板重要得多。

还有一个小技巧：代码里的 Dijkstra、Floyd、BFS 三种单源/全源最短路径模板，最好用同一种语言各背一遍，并且能互相切换。很多题表面是“找城市”，实际会包装成“找加油站”“找信号塔”“找服务中心”，识别出本质是中心点问题，你已经赢了一半。

最后再提一句，别嫌暴力 BFS 低级。它在 200 分题里至少能帮你拿到大部分测试点的分，稳扎稳打把基础模板吃透，比追求炫技写法实用得多。