PAT A1079 Total Sales of Supply Chain (25 分) 树遍历

题目大意计算由 retailers零售商, distributors经销商, and suppliers供应商组成的树最终的销售额。其中root supplier的节点编号是0初始价格是p每次向下一层价格会增加 r%直到叶子节点的 retailers并给出所有retailers的销售量。树的遍历问题由于价格和层数有关系dfs 和 bfs 都可以。dfs代码#include vector #include cstdio using namespace std; void dfs(int v, double sum, double price, double r, vectorvectorint tree, vectordouble amount) { if(tree[v].size() 0) { sum price * amount[v]; return; } for (int i 0; i tree[v].size(); i) { dfs(tree[v][i], sum, price * (1 r / 100), r, tree, amount); } } int main() { int N; double p, r; scanf(%d%lf%lf, N, p, r); vectorvectorint tree(N); vectordouble amount(N); for (int i 0; i N; i) { int childNum; scanf(%d, childNum); if(childNum 0) { for (int j 0; j childNum; j) { int child; scanf(%d, child); tree[i].push_back(child); } } else scanf(%lf, amount[i]); } double sum 0; dfs(0, sum, p, r, tree, amount); printf(%.1f, sum); return 0; }bfs代码#include vector #include cstdio #include queue using namespace std; void bfs(int root, double r, vectordouble price, vectorvectorint tree) { queueint q; q.push(root); while(!q.empty()) { int now q.front(); q.pop(); for (int i 0; i tree[now].size(); i) { price[tree[now][i]] price[now] * (1 r / 100); q.push(tree[now][i]); } } } int main() { int N; double p, r; scanf(%d%lf%lf, N, p, r); vectorvectorint tree(N); vectordouble price(N, p); vectordouble amount(N, 0); for (int i 0; i N; i) { int childNum; scanf(%d, childNum); if(childNum 0) { for (int j 0; j childNum; j) { int child; scanf(%d, child); tree[i].push_back(child); } } else scanf(%lf, amount[i]); } bfs(0, r, price, tree); double sum 0; for (int i 0; i N; i) { sum amount[i] * price[i]; } printf(%.1f, sum); return 0; }