PAT-Total Sales of Supply Chain (25)

题目来源

Total Sales of Supply Chain (25)

题目描述点击链接自行查看

注意点：

• 输出保留一位小数

思路简介

神似Highest Price in Supply Chain (25)，可以参考我的另一篇题解 这题也是先建树（我用的链式前向星） 用一个数组保存每个结点能卖的数量 广搜记录层数 h 如果一个结点可以卖出 k 份，价格就是 k*p*(1+r%)^h

遇到的问题

无，一遍过

代码

/**
* https://www.nowcoder.com/pat/5/problem/4309
* bfs
*/
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int head[N];
struct Edge{
int to,next;
}e[N];
int cnt=0;
int v[N];

void add(int u,int v){
e[cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt++;
}

int n;
double p,r;
void input(){
memset(head,–1,sizeof(head));
cin>>n>>p>>r;
for(int i=0;i<n;++i){
int k;
cin>>k;
for(int j=0;j<k;++j){
int v;
cin>>v;
add(i,v);
}
if(!k){
int value;
cin>>value;
v[i]=value;
}
}
}

void solve(){
input();
queue<int>q;

q.push(0);
int num=1,h=0;
double res;
while(!q.empty()){
int u=q.front();
q.pop();num—;
if(v[u]){
double fp=p;
for(int i=0;i<h;++i){
fp*=1+r/100;
}
res+=fp*v[u];
}

for(int i=head[u];i!=–1;i=e[i].next){
q.push(e[i].to);
}

if(num==0){
h++;num=q.size();
}
}
cout<<fixed<<setprecision(1)<<res;
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
int T=1;
//cin>>T;
while(T—){
solve();
}
return 0;
}