[PAT解题报告] Total Sales of Supply Chain
给了经销商，零售商，供应商的关系，其实就是一棵有根树，根节点售价已知，每下一层售价增加r%，这样我们可以知道每个叶节点（供应商）的售价，dfs即可。又知道每个叶节点要卖多少，所以乘一下累加就能得到最终总的收入。
我没有区分叶节点和中间节点，而是用了一个数组a，表示每个节点要卖多少，事实上非叶节点这个值是0，所以累加到总和叶没关系。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
const int N = 100005;
vector<int> con[N];
int a[N];
double p[N],total,r;
void dfs(int father,int x) {
if (father >= 0) {
p[x] = p[father] * r;
}
total += p[x] * a[x];
for (int i = 0; i < con[x].size(); ++i) {
dfs(x, con[x][i]);
}
}
int main() {
int n;
scanf("%d%lf%lf",&n,p,&r);
r = 1. + r / 100.;
for (int i = 0; i < n; ++i) {
int x;
scanf("%d",&x);
if (x == 0) {
scanf("%d",&a[i]);
}
else {
for (;x;--x) {
int y;
scanf("%d",&y);
con[i].push_back(y);
}
}
}
dfs(-1, 0);
printf("%.1lf\n",total);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1079
投递腾讯等公司10个岗位 >
