1079 Total Sales of Supply Chain (25分)

1079 Total Sales of Supply Chain (25分)

思路

就一个树形图，跑$dfs$或$bfs$，记录深度，遇到叶子结点计算贡献即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n;double p,r,ans;
int val[N];
double dep[N];
vector<int>e[N];
int main(){
    scanf("%d%lf%lf",&n,&p,&r);
    for(int i=0;i<n;i++){
        int k;scanf("%d",&k);
        if(!k){
            int v;scanf("%d",&val[i]);
        }
        for(int j=0,x;j<k;j++){
            scanf("%d",&x);
            e[i].pb(x);
        }
    }queue<int>q;
    q.push(0);
    dep[0]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        if(e[u].empty()){
            ans+=val[u]*p*dep[u];
        }
        for(int v:e[u]){
            dep[v]=dep[u]*(1+0.01*r),q.push(v); 
        }
    }
    printf("%.1f\n",ans);
    return 0;
}