跳至主要內容

【DFSBFS】2024D-寻找最富裕的小家庭

【DFSBFS】2024D-寻找最富裕的小家庭

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3514

题目描述

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

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

输入描述

第一行为一个数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

说明

所构建出的树如上图所示，其中最小富裕家庭为节点2和节点4构成的小家庭。

解题思路

常规搜索解法

题目所给的数据形式，非常容易想到转化为邻接表来储存数据。

另外，由于数据所给的编号是从1开始的，为了方便后续对应上财富列表的索引（从0开始），可以把-1之后的结果作为编号来储存。

neighbor_dic = defaultdict(list)
for _ in range(n-1):
    fa, ch = map(int, input().split())
    neighbor_dic[fa-1].append(ch-1)

另外，由于本题的输入没有告知根节点root，我们需要根据输入的n-1条边来找到根节点。

根节点root存在特点：根节点root不是任何一个节点的子节点。因此，我们可以根据n-1条边中的所有子节点，反推出唯一那个不是子节点的节点，即为根节点。具体代码如下

neighbor_dic = defaultdict(list)
children_set = set()
for _ in range(n-1):
    fa, ch = map(int, input().split())
    neighbor_dic[fa-1].append(ch-1)
    children_set.add(ch-1)

for i in range(n):
    if i not in children_set:
        root = i
        break

剩下的就是常规的DFS和BFS过程了。由于本题所给数据是树型结构（有向无环图），不会出现同一个节点多次进入的情况，因此无需额外使用check_list来维护节点重复进入。

对于DFS而言，核心函数为

def dfs(neighbor_dic, money_list, i):
    global ans
    little_family_sum = money_list[i]

    for child in neighbor_dic[i]:
        dfs(neighbor_dic, money_list, child)
        little_family_sum += money_list[child]

    ans = max(ans, little_family_sum)

对于BFS而言，核心过程为

q = deque([root])

ans = 0
while q:
    node = q.popleft()
    little_family_sum = money_list[node]
    
    for child in neighbor_dic[node]:
        q.append(child)
        little_family_sum += money_list[child]
        
    ans = max(ans, little_family_sum)

可以发现都涉及相似的过程：

  1. 考虑当前小家庭的父节点i
  2. 初始化当前小家庭的总财富值little_family_sum = money_list[i]
  3. 考虑i的所有子节点child
    1. 对child进行递归（DFS）/将child加入队列中（BFS）
    2. 根据子节点的财富money_list[ch]，更新当前小家庭的总财富值little_family_sum
  4. 基于当前小家庭的总财富值little_family_sum，更新全局的答案ans

无需搜索的简单解法

另外，本题还存在一种非常简单的解法，无需进行DFS/BFS搜索。

由于每一个小家庭仅由父节点和其子节点构成，这里的对应关系可以从边的对应关系中直接得到。

在拿到一条边(fa, ch)的时候，实际上我们可以马上知道父节点fa和子节点ch对应的财富money_list[fa]和money_list[ch]。

仅需额外构建一个列表little_family_list，little_family_list[i]表示以i为父节点的小家庭的财富。

初始化litte_family_list[i] = money_list[i]（这样才能避免父节点的重复计算），然后对于所有的边(fa, ch)，将fa的孩子ch的财富加入到这个小家庭中（只往小家庭中加入子节点），即litte_family_list[fa] += money_list[ch]。

最后找到litte_family_list中的最大值即为答案。整体的核心代码如下

little_family_list = money_list.copy()
for _ in range(n-1):
    fa, ch = map(int, input().split())
    little_family_list[fa-1] += money_list[ch-1]

print(max(little_family_list))

代码

解法一：DFS

Python

# 题目：2023C-寻找最富裕的小家庭
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问


# DFS函数
def dfs(neighbor_dic, money_list, i):
    global ans
    # 初始化当前小家庭的财富值为money_list[i]
    little_family_sum = money_list[i]

    # 考虑所有节点i的子节点child，做两件事情：
    # 1. 对child进行递归
    # 2. 更新little_family_sum的值
    for child in neighbor_dic[i]:
        dfs(neighbor_dic, money_list, child)
        little_family_sum += money_list[child]

    # 更新ans
    ans = max(ans, little_family_sum)

from collections import defaultdict

# 输入节点个数
n = int(input())
# 输入各个节点对应的财富
money_list = list(map(int, input().split()))
# 初始化邻接表
neighbor_dic = defaultdict(list)
# 储存子节点的集合，用来找根节点
children_set = set()

# 建树，输入n-1行
for _ in range(n-1):
    # 输入某一条边对应的父节点和子节点
    # 注意编号是从1开始的，为了方便使用，可以令所有的编号-1
    # 使得编号从0开始
    fa, ch = map(int, input().split())
    # 父节点的邻接表延长
    neighbor_dic[fa-1].append(ch-1)
    # ch是fa的子节点，必然不是根节点，存入children_set中
    children_set.add(ch-1)

# 寻找整棵树的根节点，唯一一个不位于children_set中的节点即为根节点
for i in range(n):
    if i not in children_set:
        root = i
        break

# 初始化ans为0
ans = 0
# 递归调用入口
dfs(neighbor_dic, money_list, root)
print(ans)

Java

import java.util.*;

public class Main {
    static int ans = 0;

    static void dfs(HashMap<Integer, List<Integer>> neighborDic, List<Integer> moneyList, int i) {
        // 初始化当前小家庭的财富值为moneyList.get(i)
        int littleFamilySum = moneyList.get(i);

        // 考虑所有节点i的子节点child，做两件事情：
        // 1. 对child进行递归
        // 2. 更新littleFamilySum的值
        List<Integer> children = neighborDic.get(i);
        if (children != null) {
            for (int child : children) {
                dfs(neighborDic, moneyList, child);
                littleFamilySum += moneyList.get(child);
            }
        }

        // 更新ans
        ans = Math.max(ans, littleFamilySum);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> moneyList = new ArrayList<>();
        HashMap<Integer, List<Integer>> neighborDic = new HashMap<>();
        HashSet<Integer> childrenSet = new HashSet<>();

        for (int i = 0; i < n; i++) {
            moneyList.add(scanner.nextInt());
        }

        for (int i = 0; i < n - 1; i++) {
            int fa = scanner.nextInt();
            int ch = scanner.nextInt();
            if (!neighborDic.containsKey(fa - 1)) {
                neighborDic.put(fa - 1, new ArrayList<>());
            }
            neighborDic.get(fa - 1).add(ch - 1);
            childrenSet.add(ch - 1);
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (!childrenSet.contains(i)) {
                root = i;
                break;
            }
        }

        dfs(neighborDic, moneyList, root);
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int ans = 0;

void dfs(unordered_map<int, vector<int>>& neighborDic, vector<int>& moneyList, int i) {
    // 初始化当前小家庭的财富值为moneyList[i]
    int littleFamilySum = moneyList[i];

    // 考虑所有节点i的子节点child，做两件事情：
    // 1. 对child进行递归
    // 2. 更新littleFamilySum的值
    for (int child : neighborDic[i]) {
        dfs(neighborDic, moneyList, child);
        littleFamilySum += moneyList[child];
    }

    // 更新ans
    ans = max(ans, littleFamilySum);
}

int main() {
    int n;
    cin >> n;
    vector<int> moneyList(n);
    unordered_map<int, vector<int>> neighborDic;
    unordered_set<int> childrenSet;

    for (int i = 0; i < n; i++) {
        cin >> moneyList[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int fa, ch;
        cin >> fa >> ch;
        neighborDic[fa - 1].push_back(ch - 1);
        childrenSet.insert(ch - 1);
    }

    int root = -1;
    for (int i = 0; i < n; i++) {
        if (childrenSet.find(i) == childrenSet.end()) {
            root = i;
            break;
        }
    }

    dfs(neighborDic, moneyList, root);
    cout << ans << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。需要遍历整棵树。

空间复杂度：O(N)，递归编译栈所占空间。

解法二：BFS

Python

# 题目：2023C-寻找最富裕的小家庭
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问

from collections import defaultdict, deque

# 输入节点个数
n = int(input())
# 输入各个节点对应的财富
money_list = list(map(int, input().split()))
# 初始化邻接表
neighbor_dic = defaultdict(list)
# 储存子节点的集合，用来找根节点
children_set = set()

# 建树，输入n-1行
for _ in range(n-1):
    # 输入某一条边对应的父节点和子节点
    # 注意编号是从1开始的，为了方便使用，可以令所有的编号-1
    # 使得编号从0开始
    fa, ch = map(int, input().split())
    # 父节点的邻接表延长
    neighbor_dic[fa-1].append(ch-1)
    # ch是fa的子节点，必然不是根节点，存入children_set中
    children_set.add(ch-1)

# 寻找整棵树的根节点，唯一一个不位于children_set中的节点即为根节点
for i in range(n):
    if i not in children_set:
        root = i
        break


# 初始化队列，包含根节点root的编号
q = deque([root])

ans = 0
# 进行BFS搜索
while q:
    # 弹出队头节点，为当前小家庭的父节点
    node = q.popleft()
    # 初始化当前小家庭的财富值为money_list[node]
    little_family_sum = money_list[node]
    # 遍历node的所有子节点child，做两件事情：
    # 1. 令child入队
    # 2. 更新little_family_sum的值
    for child in neighbor_dic[node]:
        q.append(child)
        little_family_sum += money_list[child]
    # 更新ans
    ans = max(ans, little_family_sum)

print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] moneyList = new int[n];
        Map<Integer, List<Integer>> neighborDic = new HashMap<>();
        Set<Integer> childrenSet = new HashSet<>();

        for (int i = 0; i < n; i++) {
            moneyList[i] = scanner.nextInt();
            neighborDic.put(i, new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            int fa = scanner.nextInt() - 1;
            int ch = scanner.nextInt() - 1;
            neighborDic.get(fa).add(ch);
            childrenSet.add(ch);
        }

        int root = 0;
        for (int i = 0; i < n; i++) {
            if (!childrenSet.contains(i)) {
                root = i;
                break;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(root);

        int ans = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            int littleFamilySum = moneyList[node];
            for (int child : neighborDic.get(node)) {
                queue.offer(child);
                littleFamilySum += moneyList[child];
            }
            ans = Math.max(ans, littleFamilySum);
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <set>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> moneyList(n);
    unordered_map<int, vector<int>> neighborDic;
    set<int> childrenSet;

    for (int i = 0; i < n; ++i) {
        cin >> moneyList[i];
        neighborDic[i] = vector<int>();
    }

    for (int i = 0; i < n - 1; ++i) {
        int fa, ch;
        cin >> fa >> ch;
        neighborDic[fa - 1].push_back(ch - 1);
        childrenSet.insert(ch - 1);
    }

    int root = 0;
    for (int i = 0; i < n; ++i) {
        if (childrenSet.find(i) == childrenSet.end()) {
            root = i;
            break;
        }
    }

    queue<int> q;
    q.push(root);

    int ans = 0;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        int littleFamilySum = moneyList[node];
        for (int child : neighborDic[node]) {
            q.push(child);
            littleFamilySum += moneyList[child];
        }
        ans = max(ans, littleFamilySum);
    }

    cout << ans << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。需要遍历整棵树。

空间复杂度：O(N)。q最大所占空间。

解法三：直接模拟（最简单）

Python

# 题目：2023C-寻找最富裕的小家庭
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：直接模拟
# 代码看不懂的地方，请直接在群上提问


# 输入节点个数
n = int(input())
# 输入各个节点对应的财富
money_list = list(map(int, input().split()))
# 构建小家庭财富列表，初始化为每一个节点i的财富
# little_family_list[i]表示以节点i为父节点的小家庭的财富
little_family_list = money_list.copy()

# 输入n-1行
for _ in range(n-1):
    # 输入某一条边对应的父节点和子节点
    # 注意编号是从1开始的，为了方便使用，可以令所有的编号-1
    # 使得编号从0开始
    fa, ch = map(int, input().split())
    little_family_list[fa-1] += money_list[ch-1]

# 取little_family_list中的最大值即可
print(max(little_family_list))

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] moneyList = new int[n];
        int[] littleFamilyList = new int[n];

        for (int i = 0; i < n; i++) {
            moneyList[i] = scanner.nextInt();
            littleFamilyList[i] = moneyList[i];
        }

        for (int i = 0; i < n - 1; i++) {
            int fa = scanner.nextInt();
            int ch = scanner.nextInt();
            littleFamilyList[fa - 1] += moneyList[ch - 1];
        }

        int maxWealth = Integer.MIN_VALUE;
        for (int wealth : littleFamilyList) {
            maxWealth = Math.max(maxWealth, wealth);
        }

        System.out.println(maxWealth);
    }
}

JavaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
 
void (async function () {
  const n = parseInt(await readline());
  const moneyList = (await readline()).split(" ").map(Number);
  const littleFamilyList = [...moneyList];
 
  for (let i = 0; i < n - 1; i++) {
    const [fa, ch] = (await readline()).split(" ").map(Number);
    littleFamilyList[fa-1] += moneyList[ch-1];
  }
 
  console.log(Math.max(...littleFamilyList));
})();

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> moneyList(n);
    vector<int> littleFamilyList(n);

    for (int i = 0; i < n; i++) {
        cin >> moneyList[i];
        littleFamilyList[i] = moneyList[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int fa, ch;
        cin >> fa >> ch;
        littleFamilyList[fa - 1] += moneyList[ch - 1];
    }

    int maxWealth = *max_element(littleFamilyList.begin(), littleFamilyList.end());
    cout << maxWealth << endl;

    return 0;
}

时空复杂度

时间复杂度：O(N)。需要遍历所有边。

空间复杂度：O(N)。little_family_list所占空间。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法