AcWing 1565. 供应链总销售额
原题链接
简单
作者:
eveer
,
2021-09-03 20:58:16
,
所有人可见
,
阅读 360
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;//n表示商家的数量
double price,r;//price表示厂商给出的批发价,r表示折扣
vector<int>chain[N];//记录每一个商家下面是否还有子商家
int sale[N];//记录每一个点的销售数量,如果不是零售店,那么销售数量等于0
int level[N];//层序遍历
int nlevel[N];//记录每一个节点的层序
bool is_ret[N];//记录当前节点是否为零售商
void bfs(int root)
{
int tt=0,hh=0;
level[++tt]=root;//将根节点存入
nlevel[tt]=0;
while(tt>hh)
{
int para=level[++hh];//记录当前的父亲节点
if(chain[para].size()!=0)//如果当前存在子节点,那么将其加入
{
for(int i=0;i<chain[para].size();i++)
{
level[++tt]=chain[para][i];
nlevel[tt]=nlevel[hh]+1;
}
}
}
}
int main()
{
memset(nlevel,-1,sizeof nlevel);
scanf("%d %lf %lf",&n,&price,&r);
for(int i=0;i<n;i++)
{
int num;
scanf("%d",&num);
if(num==0)//表示这个已经是零售店了
{
int x;
scanf("%d",&x);//记录零售店卖的数量
sale[i]=x;
is_ret[i]=true;//表示当前为零售商
}
else//表示当前不是零售店
{
for(int j=0;j<num;j++)//将当前的子节点存入
{
int x;
scanf("%d",&x);
chain[i].push_back(x);
}
}
}
bfs(0);
double sum=0;//记录最终获得总售卖
for(int i=1;i<=n;i++)
{
if(is_ret[level[i]]==true)//判断层次序列中的第i个节点的是否为零售商,如果是
sum+=price*pow(1+r/100,nlevel[i])*sale[level[i]];
}
printf("%.1lf",sum);
return 0;
}