在浩瀚无垠的宇宙中,散布着无数的星系。一部分星系之间通过稳定的“星际航道”紧密相连,形成一个个“星系联盟”。在本题的设定里,一个星系联盟由一个或多个通过星际航道直接或间接相连的星系构成,这在图论中被称为一个 无向图的连通分量 。 每个星系都拥有一个独一无二的“文明等级”,这是一个正整数,代表了该星系文明的繁荣程度。而一个星系联盟的总实力,则定义为该联盟内所有星系文明等级之和。 现在,作为星际探险家的您,得到了一份星图。这份星图包含了各个星系的文明等级信息,以及它们之间的星际航道连接情况。您的任务是: 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 时,表示星系之间没有任何航道,每个星系都是一个独立的联盟。
请输出一行,包含两项内容,以空格隔开:在总实力最强的星系联盟中,文明等级最高的星系的名称,以及该联盟的总实力。 题目保证所有星系的文明等级各不相同,并且总实力最强的星系联盟是唯一的。
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 | 标准输入输出
参考方向:图
把关系抽象成点与边,再按问的类型选遍历/最短路/连通性算法。
思路框架(图 通法 · 非本题专属)
实现要点:注意是有向图还是无向图,无向图加边记得双向。
复杂度:时间 O(V+E) 遍历 / O(E log V) Dijkstra | 空间 O(V+E)
该范式的通法易错点
对照本题
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。
样例 1
10 / 21hjdgv0vj 6587 / 3j82e2tmk2 7928 / 43hhi7u8f8 6659 / 80htg9ud23 6957 / 8b96bgxl55 8524 / bf98w33f47 8692 / i1b09lbu79 5801 / nuy3c55lznuy3c55lzm 52845解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。
本题来源:2025年秋招-华为-9月3号开发岗。