1079. Total Sales of Supply Chai

PAT-A 1079，题目地址：https://www.patest.cn/contests/pat-a-practise/1079
题意：要计算的是所有retailer把东西都卖给customer后，所有retailers卖出的货物的总价
思路：

1. 根据题意建树，root就是顶级供应商
2. 对数目进行宽搜，计算出每个retailer的深度
3. 根据深度计算总的销售额

注意： r是一个百分比值，因此每层的价格是上一层的（1+r/100）倍

代码：

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

struct Node{
    int level; //该节点深度是多少，其中根节点为0
    int *children; //记录这个节点的所有孩子
    int amount; //如果是retailer，则他有多少货物
    int count; //孩子数量
    Node(): count(0), amount(0), level(0), children(NULL){}
};

int main(){
    int n;
    double p, r;
    cin >> n >> p >> r;
    Node* nodes = new Node[n];
    for(int i = 0; i < n; i++){
        int count;
        cin >> count;
        nodes[i].count = count;
        if(count == 0){
            cin >> nodes[i].amount; //他是retailer
        }
        else{
            nodes[i].children = new int[count];
            for(int j = 0; j < count; j++){
                cin >> nodes[i].children[j];
            }
        }
    }
    double res = 0;
    queue<int> q;
    nodes[0].level = 0; //根节点深度为0
    q.push(0);
//下面这个循环是宽搜的过程，搜索时顺便计算每个叶子的深度
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i = 0; i < nodes[now].count; i++){
            int child = nodes[now].children[i];
            nodes[child].level = nodes[now].level + 1;
            q.push(child);
        }
        if(nodes[now].count == 0){
            res += nodes[now].amount * p * pow(1 + r/100, nodes[now].level);
        }
    }
    printf("%.1f\n", res);
    return 0;
}