PAT A1079 Total Sales of Supply Chain [树的遍历]

题目描述

链接
给一棵树，在树根出货物的价格为p，然后从根结点开始每往下走一层，该层的货物价格将会在父亲结点的价格上增加r%，给出每个叶结点的货物量，求他们的价格之和

分析

• supply chain看作一棵树
• 其他注意点在代码中

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

const int maxn = 1e5+10;
int n,k,id;
double p,r;

struct node{
    int data;
    vector<int> child;
}nodes[maxn];

double ans;
void dfs(int root, int m){ //把m作为dfs的一个参数
    if(nodes[root].child.size()==0){
        ans += pow(1+r/100, m) * p * nodes[root].data;
        return;
    }
    for(int i=0;i<nodes[root].child.size();i++){
        dfs(nodes[root].child[i], m+1);
    }
}

int main(){
    scanf("%d%lf%lf",&n,&p,&r);
    for(int i=0;i<n;i++){
        scanf("%d",&k);
        if(k != 0){
            for(int j=0;j<k;j++){
                scanf("%d",&id);
                nodes[i].child.push_back(id);
            }
        }else{
            scanf("%d",&nodes[i].data);
        }
    }
    dfs(0, 0); //是0不是-1,因为还要计算零售商卖给顾客
    printf("%.1f
", ans);
}