题解 | #探索宇宙中的星系联盟#

题目链接

题目描述

给定一张星图，包含 $N$ 个星系和 $M$ 条连接星系的星际航道。每个星系都有一个唯一的名称和文明等级。通过星际航道直接或间接相连的星系组成一个“星系联盟”。一个联盟的总实力是其内部所有星系文明等级的总和。任务是找出总实力最强的那个联盟，并输出该联盟中文明等级最高的星系名称及其总实力。

解题思路

这个问题可以抽象为图论中的寻找连通分量问题。每个星系是一个节点，每条星际航道是一条无向边。一个星系联盟就是一个图的连通分量。我们需要计算每个连通分量的节点权重（文明等级）之和，并找出权重和最大的那个连通分量。

使用 并查集 (Disjoint Set Union, DSU) 是解决此类问题的经典且高效的数据结构。算法步骤如下：

数据初始化：
- 由于星系名称是字符串，为了方便处理，我们先用一个哈希表（map）将每个星系名称映射到一个从 $0$ 到 $N-1$ 的唯一整数 $ID$ 。
- 创建一个并查集结构，初始时，每个星系都各自属于一个独立的集合（联盟）。
- 为每个集合（联盟）维护两个属性：联盟的总实力 total_strength 和联盟内文明等级最高的星系 $ID$ max_level_id。初始时，每个联盟的总实力就是该星系自身的文明等级，最高等级星系 $ID$ 也是它自己。
构建联盟：
- 遍历所有 $M$ 条星际航道。对于每条连接星系 $A$ 和星系 $B$ 的航道：
- 找到 $A$ 和 $B$ 所在集合的根节点 rootA 和 rootB。
- 如果 rootA 和 rootB 不相同，说明 $A$ 和 $B$ 分属不同的联盟，需要将它们合并（union）。
- 合并时，将一个集合（例如 rootB 的集合）合并到另一个集合（rootA 的集合）中。同时，更新合并后新联盟的信息：
  - 总实力： $total\_strength[rootA] = total\_strength[rootA] + total\_strength[rootB]$ 。
  - 最高文明等级星系：比较 rootA 和 rootB 两个联盟中文明等级最高的星系，将等级更高者的 $ID$ 作为新联盟的 $max\_level\_id[rootA]$ 。
寻找最强联盟：
- 处理完所有航道后，图的连通结构已经通过并查集建立起来了。
- 遍历所有星系 $i$ 从 $0$ 到 $N-1$ 。如果星系 $i$ 是其所在集合的根节点（即 $parent[i] == i$ ），那么它就代表一个最终形成的联盟。
- 比较该联盟的总实力 $total\_strength[i]$ 与记录的全局最强联盟实力 $max\_strength$ 。如果 $total\_strength[i]$ 更大，则更新 $max\_strength$ 和最强联盟中等级最高的星系名称。
输出结果：
- 遍历结束后，即可得到最强联盟的各项信息，按要求输出。

这种方法通过路径压缩和按秩（或大小）合并的优化，可以接近线性时间复杂度完成所有合并和查找操作，非常高效。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <map>

using namespace std;

// 并查集查找操作（带路径压缩）
int find_set(int v, vector<int>& parent) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v], parent);
}

// 并查集合并操作
void unite_sets(int a, int b, vector<int>& parent, vector<long long>& total_strength, vector<int>& max_level_id, const vector<int>& levels) {
    a = find_set(a, parent);
    b = find_set(b, parent);
    if (a != b) {
        // 为了简化，总是将 b 合并到 a
        parent[b] = a;
        total_strength[a] += total_strength[b];
        // 更新联盟中文明等级最高的星系ID
        if (levels[max_level_id[b]] > levels[max_level_id[a]]) {
            max_level_id[a] = max_level_id[b];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    map<string, int> name_to_id;
    vector<string> id_to_name(n);
    vector<int> levels(n);
    vector<int> parent(n);
    vector<long long> total_strength(n);
    vector<int> max_level_id(n);

    // 初始化数据
    for (int i = 0; i < n; ++i) {
        cin >> id_to_name[i] >> levels[i];
        name_to_id[id_to_name[i]] = i;
        parent[i] = i; // 每个星系自成一个联盟
        total_strength[i] = levels[i];
        max_level_id[i] = i;
    }

    int m;
    cin >> m;

    // 合并联盟
    for (int i = 0; i < m; ++i) {
        string name1, name2;
        cin >> name1 >> name2;
        unite_sets(name_to_id[name1], name_to_id[name2], parent, total_strength, max_level_id, levels);
    }

    long long max_strength = -1;
    string top_star_name = "";

    // 查找最强联盟
    for (int i = 0; i < n; ++i) {
        if (parent[i] == i) { // 是一个联盟的根节点
            if (total_strength[i] > max_strength) {
                max_strength = total_strength[i];
                top_star_name = id_to_name[max_level_id[i]];
            }
        }
    }

    cout << top_star_name << " " << max_strength << "\n";

    return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int[] parent;
    static long[] totalStrength;
    static int[] maxLevelId;
    static int[] levels;
    static String[] idToName;

    // 并查集查找操作（带路径压缩）
    public static int findSet(int v) {
        if (v == parent[v]) {
            return v;
        }
        parent[v] = findSet(parent[v]);
        return parent[v];
    }

    // 并查集合并操作
    public static void uniteSets(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (a != b) {
            parent[b] = a;
            totalStrength[a] += totalStrength[b];
            if (levels[maxLevelId[b]] > levels[maxLevelId[a]]) {
                maxLevelId[a] = maxLevelId[b];
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        Map<String, Integer> nameToId = new HashMap<>();
        idToName = new String[n];
        levels = new int[n];
        parent = new int[n];
        totalStrength = new long[n];
        maxLevelId = new int[n];

        // 初始化数据
        for (int i = 0; i < n; i++) {
            idToName[i] = sc.next();
            levels[i] = sc.nextInt();
            nameToId.put(idToName[i], i);
            parent[i] = i; // 每个星系自成一个联盟
            totalStrength[i] = levels[i];
            maxLevelId[i] = i;
        }

        int m = sc.nextInt();

        // 合并联盟
        for (int i = 0; i < m; i++) {
            String name1 = sc.next();
            String name2 = sc.next();
            uniteSets(nameToId.get(name1), nameToId.get(name2));
        }

        long maxStrength = -1;
        String topStarName = "";

        // 查找最强联盟
        for (int i = 0; i < n; i++) {
            if (parent[i] == i) { // 是一个联盟的根节点
                if (totalStrength[i] > maxStrength) {
                    maxStrength = totalStrength[i];
                    topStarName = idToName[maxLevelId[i]];
                }
            }
        }
        System.out.println(topStarName + " " + maxStrength);
    }
}

import sys

# 为了处理大规模递归，增加递归深度限制
sys.setrecursionlimit(200000)

# 并查集查找操作（带路径压缩）
def find_set(v, parent):
    if v == parent[v]:
        return v
    parent[v] = find_set(parent[v], parent)
    return parent[v]

# 并查集合并操作
def unite_sets(a, b, parent, total_strength, max_level_id, levels):
    a = find_set(a, parent)
    b = find_set(b, parent)
    if a != b:
        parent[b] = a
        total_strength[a] += total_strength[b]
        # 更新联盟中文明等级最高的星系ID
        if levels[max_level_id[b]] > levels[max_level_id[a]]:
            max_level_id[a] = max_level_id[b]

def main():
    # 使用sys.stdin.readline以提高IO效率
    lines = sys.stdin.readlines()
    line_idx = 0

    n = int(lines[line_idx].strip())
    line_idx += 1
    
    name_to_id = {}
    id_to_name = [""] * n
    levels = [0] * n
    parent = list(range(n))
    total_strength = [0] * n
    max_level_id = list(range(n))

    # 初始化数据
    for i in range(n):
        name, level_str = lines[line_idx].strip().split()
        line_idx += 1
        level = int(level_str)
        name_to_id[name] = i
        id_to_name[i] = name
        levels[i] = level
        total_strength[i] = level

    m = int(lines[line_idx].strip())
    line_idx += 1

    # 合并联盟
    for _ in range(m):
        name1, name2 = lines[line_idx].strip().split()
        line_idx += 1
        unite_sets(name_to_id[name1], name_to_id[name2], parent, total_strength, max_level_id, levels)

    max_strength = -1
    top_star_name = ""

    # 查找最强联盟
    for i in range(n):
        if parent[i] == i: # 是一个联盟的根节点
            if total_strength[i] > max_strength:
                max_strength = total_strength[i]
                top_star_name = id_to_name[max_level_id[i]]

    print(f"{top_star_name} {max_strength}")

if __name__ == "__main__":
    main()

算法及复杂度

算法：并查集 (Disjoint Set Union)
时间复杂度： $O(N + M \cdot \alpha(N))$ ，其中 $N$ 是星系数量， $M$ 是航道数量， $\alpha(N)$ 是反阿克曼函数，其增长非常缓慢，对于本题的数据范围可视为一个极小的常数。复杂度主要由读取输入和处理 $M$ 条航道决定，接近线性。
空间复杂度： $O(N)$ ，用于存储星系信息、名称到 $ID$ 的映射以及并查集所需的数组。