题解

题面描述

本题定义的连通网络，是由有连接关系的一个或多个节点组成的无向图。

• 图中有$n$个节点，$n$ 的取值范围为 $[1,160]$。
• 每个节点有一个唯一的权重，权重的取值范围为 $[1,10000]$。
• 节点之间有$m$条连接关系，$m$的取值范围为 $[0,160]$，每条连接表示无向边。
• 一个连通网络的权重定义为其所有节点权重之和；因为节点权重互不相同，连通网络内部可以确定“权重最大的节点”。
• 要求：找到权重最大的连通网络，输出该网络中权重最大的节点的名称，以及该网络的总权重。题目保证不同连通网络的总权重不会相同。

思路

1. 建图与遍历

   • 将节点按照名称映射为索引，记录每个节点的权重和名称。
   • 构建邻接表表示无向图。

2. 连通分量搜索

   • 对每个未访问节点，启动一次深度优先搜索（DFS）或广度优先搜索（BFS），遍历其所属连通分量。
   • 在遍历过程中，累计该分量的权重和，同时维护该分量内部权重最大的节点。

3. 结果更新

   • 每处理完一个连通分量，即可得到该分量的总权重$S$以及最大权重节点名称$name_{max}$。
   • 用一个全局变量记录迄今为止最大的连通分量权重及对应节点。

4. 输出

   • 遍历完成后，直接输出全局记录的最大节点名称与对应分量权重。

代码实现

C++

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;  // 节点数 n
    unordered_map<string, int> id;       // 节点名称到索引的映射
    vector<string> names(n);
    vector<int> weight(n);
    for (int i = 0; i < n; i++) {
        cin >> names[i] >> weight[i];
        id[names[i]] = i;
    }

    int m;
    cin >> m;  // 边数 m
    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        string u, v;
        cin >> u >> v;
        int iu = id[u], iv = id[v];
        adj[iu].push_back(iv);
        adj[iv].push_back(iu);
    }

    vector<bool> vis(n, false);
    long long bestSum = 0;    // 当前最大连通分量权重
    string bestNode;          // 对应最大节点名称

    // DFS 遍历函数
    function<void(int, long long&, int&)> dfs = [&](int u, long long& sum, int& maxIdx) {
        vis[u] = true;
        sum += weight[u];
        if (weight[u] > weight[maxIdx]) {
            maxIdx = u;
        }
        for (int v : adj[u]) {
            if (!vis[v]) dfs(v, sum, maxIdx);
        }
    };

    // 遍历所有节点，找到各连通分量
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            long long sum = 0;
            int maxIdx = i;
            dfs(i, sum, maxIdx);
            // 更新全局最优
            if (sum > bestSum) {
                bestSum = sum;
                bestNode = names[maxIdx];
            }
        }
    }

    // 输出结果
    cout << bestNode << " " << bestSum << "\n";
    return 0;
}

Python

import sys
sys.setrecursionlimit(10000)

def main():
    n = int(sys.stdin.readline().strip())  # 节点数 n
    id_map = {}
    names = []
    weight = []
    for i in range(n):
        line = sys.stdin.readline().split()
        names.append(line[0])
        weight.append(int(line[1]))
        id_map[line[0]] = i

    m = int(sys.stdin.readline().strip())  # 边数 m
    adj = [[] for _ in range(n)]
    for _ in range(m):
        u, v = sys.stdin.readline().split()
        iu, iv = id_map[u], id_map[v]
        adj[iu].append(iv)
        adj[iv].append(iu)

    visited = [False] * n
    best_sum = 0
    best_node = ""

    def dfs(u):
        """返回当前连通分量的 (sum, max_idx)"""
        visited[u] = True
        total = weight[u]
        max_idx = u
        for v in adj[u]:
            if not visited[v]:
                s, mi = dfs(v)
                total += s
                if weight[mi] > weight[max_idx]:
                    max_idx = mi
        return total, max_idx

    for i in range(n):
        if not visited[i]:
            s, mi = dfs(i)
            if s > best_sum:
                best_sum = s
                best_node = names[mi]

    print(best_node, best_sum)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static List<List<Integer>> adj;
    static String[] names;
    static int[] weight;
    static boolean[] visited;
    static long bestSum = 0;
    static String bestNode = "";

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());  // 节点数 n
        names = new String[n];
        weight = new int[n];
        Map<String, Integer> idMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().split(" ");
            names[i] = parts[0];
            weight[i] = Integer.parseInt(parts[1]);
            idMap.put(names[i], i);
        }

        m = Integer.parseInt(br.readLine().trim());  // 边数 m
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            String[] edge = br.readLine().split(" ");
            int u = idMap.get(edge[0]);
            int v = idMap.get(edge[1]);
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                long sum = dfs(i);
                // dfs 中已全局更新 bestSum & bestNode
            }
        }

        System.out.println(bestNode + " " + bestSum);
    }

    // 返回当前连通分量的权重总和，并在过程中更新 bestSum、bestNode
    static long dfs(int u) {
        visited[u] = true;
        long sum = weight[u];
        int maxIdx = u;
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                long s = dfs(v);
                sum += s;
                // 无法直接拿到子分量的局部最大 idx，故改用全局比较
            }
        }
        // 这里单节点比较，实际只需在主循环后再额外一次遍历即可简化
        if (sum > bestSum) {
            // 在该分量中找到权重最大的节点
            int curMax = u;
            for (int i = 0; i < n; i++) {
                if (visited[i] && weight[i] > weight[curMax]) {
                    curMax = i;
                }
            }
            bestSum = sum;
            bestNode = names[curMax];
        }
        return sum;
    }
}

题目内容

本题定义的连通网络，是由有连接关系的一个或多个节点组成的无向图。

连通网络中每个节点，都赋予了一个权重，表示该节点的重要程度；所有节点的权重的和，代表该连通网络的权重。

假设一个连通网络中各个节点，权重都是唯一的，不会重复。

请根据输入的节点和权重，以及节点的连接关系，分析输入包含的连通网络并计算连通网络对应的权重，最终输出权重最大网络中权重最大的节点的名称，以及该网络整体的权重。

输入描述

第一行是节点数 $n$ ，值的范围 $[1,160]$ 。

接下来会出现n行，每一行的第一个输入是节点的名称（长度小于等于 $32$ 的字符串，只包含小写字母和数字），第二个是节点的权重，通过空格和节点名称分开，权重值的范围是 $[1,10000]$ 。

接着是节点连接关系的数量 $m$ ，值的范围 $[0,160]$

接下来会出现 $m$ 行，每一行包含两个节点的名称，表示有连接关系的两个节点，节点顺序不分先后，且节点名称均包含在上面的节点列表中。如果为 $0$ ，代表节点间没有连接关系。

输出描述

找到权重最大的连通网络，输出权重最大的节点的名称，以及网络对应的权重（用例保证不同网络的权重不会相同）

样例1

输入

5
node1 15
node2 12
node3 13
node4 4
node5 50
3
node1 node2
node3 node2
node4 node5

输出

node5 54

说明

如下图，以上输入，形成了两个连通网络，$node1、node2、node3$ 有连接关系，形成连通网络 $1$ ，权重最大的节点是 $node1$ ，所有节点和是 $40$ ；$node4、node5$ 有连接关系，形成连通网络 $2$ ，权重最大的节点是 $node5$ ，所有也点和是 $54$ 。权重最大的网络的权重是 $54$ ，所以输出 $node5$ $54$ 。

样例2

输入

1
node1 100
0

输出

node1 100

说明

如下图，以上输入，形成了一个连通网络，该连通网络只有一个节点 $node1$ ，所以权重最大的节点也是 $node1$ ，所有节点和是 $100$ ，所以输出 $node1$ $100$ 。