- it
- 1079 Total Sales of Supply Chain (25 分)
层序遍历，遍历到父节点时给出子节点所在层次即父节点层号加一，遍历到叶节点时把物品数量与价格（本零售商的价格）的乘积加到sum中
也可用深度遍历，递归时深度作参数
#include <iostream>
#include <vector>
#include <math.h>
using namespace std
;
#define maxn 100000
struct node
{
vector
<int>children
;
int isLeave
=0;
int amount
;
int level
;
}t
[maxn
];
int n
;
double price
,rate
;
int main(){
cin
>>n
>>price
>>rate
;
for (int i
= 0; i
< n
; ++i
) {
int num
;
cin
>>num
;
if(num
==0){
t
[i
].isLeave
=1;
cin
>>t
[i
].amount
;
continue;
}
for (int j
= 0; j
< num
; ++j
) {
int child
;
cin
>>child
;
t
[i
].children
.push_back(child
);
}
}
double sum
=0;
node queue
[maxn
];
int rear
=0;
int front
=0;
t
[0].level
=0;
queue
[rear
++]=t
[0];
while(front
!=rear
){
node temp
=queue
[front
++];
if(temp
.isLeave
==1){
sum
+=price
*temp
.amount
*pow(1.0+rate
/100.0,temp
.level
);
continue;
}
for (int i
= 0; i
< temp
.children
.size(); ++i
) {
t
[temp
.children
[i
]].level
=temp
.level
+1;
queue
[rear
++]=t
[temp
.children
[i
]];
}
}
printf("%.1f\n",sum
);
return 0;
}
