返回目录

题目描述

在一颗树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为一个小家庭。

现给你一颗树，请计算出最富裕的小家庭的财富和。

输入描述

第一行为一个数 N，表示成员总数，成员编号 1\~N。1 ≤ N ≤ 1000

第二行为 N 个空格分隔的数，表示编号 1\~N 的成员的财富值。0 ≤ 财富值 ≤ 1000000

接下来 N -1 行，每行两个空格分隔的整数（N1, N2），表示 N1 是 N2 的父节点。

输出描述

最富裕的小家庭的财富和

示例：

输    入4
100     200      300      500
1          2
1          3
2          4
输     出700
说     明
               		3.png
成员1，2，3 组成的小家庭财富值为600
成员2，4 组成的小家庭财富值为700

题目解析

简单的逻辑分析题。

由于题目输入会给出 树形结构 中，父节点->子节点 的信息，比如下面红色部分

4
100 200 300 500
1 2
1 3
2 4

因此我们遍历这些信息时，就可以直接将子节点的财富，汇总到其父节点上。

具体实现是，由第二行输入解析得到每个节点的财富值数组 wealth。

然后根据第三行\~最后一行的输入：fa ch，执行 wealth[fa] += wealth[ch]，即将子节点的财富值汇总到父节点上。

这样最终wealth数组的最大值就是题解。

需要注意的是，题目规定成员编号 1\~N，因此定义wealth数组时，我们应该将其长度定义为N+1，且从索引1开始操作，来匹配成员编号1\~N。

wealth[fa] += wealth[ch]

存在问题。

比如下面用例：

5
100 200 300 400 500
3 4
3 5
1 3
1 2

Python算法源码

def main():
    n = int(input())

    # 创建财富和家庭财富数组，索引对应成员编号
    wealth = [0] + list(map(int, input().split()))
    family = wealth[:]

    # 计算家庭财富
    for _ in range(n - 1):
        fa, ch = map(int, input().split())
        family[fa] += wealth[ch]

    # 找出最大家庭财富
    max_wealth = max(family)

    print(max_wealth)

if __name__ == "__main__":
    main()

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 输入成员数量
        int n = sc.nextInt();

        // 创建存储财富和家庭财富的数组，其中索引对应成员编号
        int[] wealth = new int[n + 1];
        int[] family = new int[n + 1];
      
        // 输入每个成员的财富并初始化家庭财富数组
        for (int i = 1; i <= n; i++) {
            wealth[i] = sc.nextInt();
            family[i] = wealth[i];
        }

        // 输入家庭关系并计算家庭财富
        for (int i = 0; i < n - 1; i++) {
            int fa = sc.nextInt(); // 父节点
            int ch = sc.nextInt(); // 子节点
            family[fa] += wealth[ch]; // 将子节点的财富加到父节点的家庭财富中
        }

        // 找出最大的家庭财富
        int max = family[1];
        for (int i = 2; i <= n; i++) {
            if (family[i] > max) {
                max = family[i];
            }
        }

        // 输出最大的家庭财富
        System.out.println(max);
    }
}

C算法源码

def main():
    n = int(input())

    # 定义长度为n+1的wealth数组，使得wealth数组索引对应成员编号 1~N
    wealth = [0] * (n + 1)
    family = [0] * (n + 1)

    # 初始化数组
    for i in range(1, n + 1):
        wealth[i] = int(input())
        family[i] = wealth[i]

    # 输入家庭关系并计算家庭财富
    for i in range(n - 1):
        fa, ch = map(int, input().split())
        family[fa] += wealth[ch]

    # 找出最大家庭财富并打印
    max_wealth = max(family)
    print(max_wealth)

if __name__ == "__main__":
    main()
最后修改：2024 年 03 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏