华为 · 图 · 算法编程题
华为 n ≤ 32 时限 1 秒 / 256 MB

题目描述

在浩瀚无垠的宇宙中,散布着无数的星系。一部分星系之间通过稳定的“星际航道”紧密相连,形成一个个“星系联盟”。在本题的设定里,一个星系联盟由一个或多个通过星际航道直接或间接相连的星系构成,这在图论中被称为一个 无向图的连通分量 。
每个星系都拥有一个独一无二的“文明等级”,这是一个正整数,代表了该星系文明的繁荣程度。而一个星系联盟的总实力,则定义为该联盟内所有星系文明等级之和。
现在,作为星际探险家的您,得到了一份星图。这份星图包含了各个星系的文明等级信息,以及它们之间的星际航道连接情况。您的任务是:
1. 分析这份星图,找出其中所有独立的星系联盟。
2. 计算每个星系联盟的总实力。
3. 在所有联盟中,找到总实力最强的那一个。
4. 最终,请报告这个最强联盟中,文明等级最高的那个星系的名称,以及该联盟的总实力。

输入输出

输入描述
输入数据描述了一张包含 n 个星系和 m 条星际航道的星图。
- 第一行是一个整数 n ,代表星系的总数。 n 的取值范围为 [1, 160] 。
- 接下来 n 行,每行描述一个星系。格式为 `星系名称 文明等级`。
- `星系名称` 是一个长度不超过 32 的字符串,仅由小写字母和数字组成。
- `文明等级` 是一个整数,其取值范围为 [1, 10000] 。
- 之后的一行是一个整数 m ,代表星际航道的总数。 m 的取值范围为 [0, 160] 。
- 随后的 m 行,每行描述一条星际航道,格式为 `星系A名称 星系B名称`,表示星系 A 与星系 B 之间存在一条双向航道。输入保证这里出现的星系名称都已在前文中定义过。
- 特别地,当 m=0 时,表示星系之间没有任何航道,每个星系都是一个独立的联盟。
输出描述
请输出一行,包含两项内容,以空格隔开:在总实力最强的星系联盟中,文明等级最高的星系的名称,以及该联盟的总实力。
题目保证所有星系的文明等级各不相同,并且总实力最强的星系联盟是唯一的。

样例共 1 组

样例 1
输入
10
21hjdgv0vj 6587
3j82e2tmk2 7928
43hhi7u8f8 6659
80htg9ud23 6957
8b96bgxl55 8524
bf98w33f47 8692
i1b09lbu79 5801
nuy3c55lzm 9341
r371vsjr84 7467
wj7x829uc1 2438
8
3j82e2tmk2 80htg9ud23
43hhi7u8f8 80htg9ud23
43hhi7u8f8 bf98w33f47
43hhi7u8f8 r371vsjr84
80htg9ud23 r371vsjr84
8b96bgxl55 wj7x829uc1
i1b09lbu79 nuy3c55lzm
i1b09lbu79 r371vsjr84
输出
nuy3c55lzm 52845

算法解析依据一般

考点:图

数据规模 n ≤ 32 | 限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 数据规模:n ≤ 32
  • 复杂度门槛:允许 O(n³) ~ O(n⁴) 的多重循环,可以放心枚举。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:图

把关系抽象成点与边,再按问的类型选遍历/最短路/连通性算法。

思路框架(图 通法 · 非本题专属)

  1. 建图:邻接表(稀疏)或邻接矩阵(稠密)。
  2. 问「最少几步 / 最短路径」且边权为 1 → BFS。
  3. 问「是否连通 / 需要加几条边连通」→ 并查集 / 连通块计数。
  4. 问「带权最短路」→ Dijkstra(非负权)或 Floyd(点数小、多源)。
  5. 问「依赖顺序」→ 拓扑排序。

实现要点:注意是有向图还是无向图,无向图加边记得双向。

复杂度:时间 O(V+E) 遍历 / O(E log V) Dijkstra | 空间 O(V+E)

该范式的通法易错点

  • 无向图只加了单向边。
  • BFS 入队时没标记访问,导致重复入队。

对照本题

  • 数据规模 n ≤ 32,允许 O(n³) ~ O(n⁴) 的多重循环,可以放心枚举。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:10 / 21hjdgv0vj 6587 / 3j82e2tmk2 7928 / 43hhi7u8f8 6659 / 80htg9ud23 6957 / 8b96bgxl55 8524 / bf98w33f47 8692 / i1b09lbu79 5801 / nuy3c55lz
  • 输出:nuy3c55lzm 52845

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:2025年秋招-华为-9月3号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解