E卷-boss的收入(100分)

boss的收入

问题描述

一个XX产品行销总公司只有一个 boss，其下有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销。

规定，每个月，下级分销需要将自己的总收入（自己的+下级上交的）每满 100 元上交 15 元给自己的上级。

现给出一组分销的关系和每个分销的收入，请找出 boss 并计算出这个 boss 的收入。

比如：

• 收入 100 元，上交 15 元；
• 收入 199 元（99 元不够 100），上交 15 元；
• 收入 200 元，上交 30 元。

提示：输入的数据只存在 1 个 boss，不存在环路

输入格式

第一行输入一个整数 ，表示关系的总数量。

接下来 行，每行输入三个整数 、 和 ，分别表示分销 ID、上级分销 ID 和收入。

输出格式

输出两个整数，分别表示 boss 的 ID 和总收入，用空格分隔。

样例输入

5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200

样例输出

0 120

样例解释

在这个例子中：

1. 分销 1 收入 100 元，上交 15 元
2. 分销 2 收入 199 元，上交 15 元
3. 分销 3 收入 200 元，上交 30 元
4. 分销 4 收入 200 元，上交 30 元
5. 分销 5 收入 200 元，上交 30 元

所有分销的上级都是 0，因此 0 是 boss。boss 的总收入为 15 + 15 + 30 + 30 + 30 = 120 元。

数据范围

• 分销 ID 范围：
• 收入范围：，单位为元
• 

题解

这道题的核心在于理解分销系统的层级结构和收入上交规则。

解题思路如下：

1. 构建分销关系图：使用字典存储每个分销的上级和下级关系。

2. 计算收入：从叶子节点（没有下级的分销）开始，自底向上计算每个分销的实际收入。

3. 找到 boss：boss 是唯一没有上级的分销。

4. 深度优先搜索（DFS）：使用 DFS 遍历整个分销树，计算每个节点的总收入。

关键点在于理解收入的计算方式：每个分销的收入包括自己的收入和从下级上交的收入。上交给上级的金额是总收入每满 100 元上交 15 元。

例如，考虑这样一个简单的分销链：

A (收入 100) -> B (收入 150) -> C (boss)

计算过程如下：

1. A 上交给 B：100 // 100 * 15 = 15
2. B 的总收入：150 + 15 = 165
3. B 上交给 C：165 // 100 * 15 = 15
4. C 的总收入：15

使用 DFS 可以有效地处理这种层级结构，时间复杂度为 O(N)，其中 N 是分销的数量。这对于给定的数据范围（N ≤ 10000）来说是完全可以接受的。

这个解法的优点在于它直观地模拟了实际的收入计算过程，同时通过使用字典和 DFS，有效地处理了复杂的层级关系。

参考代码

• Python

def dfs(node):
    """
    深度优先搜索函数，计算每个节点的总收入
    :param node: 当前节点
    :return: 无返回值，直接修改 income 字典
    """
    children = child_parent.get(node, [])
    if not children:  # 如果是叶子节点，直接返回
        return
    
    for child in children:
        dfs(child)  # 递归处理子节点
        # 计算子节点上交的收入并加到当前节点
        income[node] += (income[child] // 100) * 15

def find_boss():
    """
    找到 boss 并计算其总收入
    :return: boss 的 ID 和总收入
    """
    for agent in agents:
        if agent not in parent_child:  # 没有上级的就是 boss
            income[agent] = 0  # 初始化 boss 的收入为 0
            dfs(agent)  # 从 boss 开始深度优先搜索
            return f"{agent} {income[agent]}"

# 读取输入
n = int(input())  # 关系总数

income = {}  # 存储每个分销的收入
agents = set()  # 存储所有分销 ID
parent_child = {}  # 存储父子关系
child_parent = {}  # 存储子父关系

# 处理输入数据
for _ in range(n):
    child_id, parent_id, child_income = input().split()
    child_id, parent_id, child_income = int(child_id), int(parent_id), int(child_income)
    
    income[child_id] = child_income  # 记录初始收入
    agents.add(child_id)
    agents.ad