1079. Total Sales of Supply Chain (25)

思路

首先记录各个节点的上下级关系,然后深度优先遍历更新各个节点的price,最后将所有节点的stock(如果不是零售商则为0)和对应的price相乘得到。

代码

#include <iostream>
#include <vector>
#include <cstring>
#define MAX 100000
using namespace std;
int n;
double rootPrice,percent;
double price[MAX];
double stock[MAX];
vector<vector<int> > chain;
int updatePrice(int curid, double curPrice)//深度优先更新价格
{
    for(int i=0;i<chain[curid].size();i++)
    {
        int child = chain[curid][i];
        if(child != -1)
        {
            price[child] = curPrice * (1+(double)percent/100);
            updatePrice(child, price[child]);
        }
    }
    return 0;
}
int main()
{
    cin>>n>>rootPrice>>percent;
    memset(price,0,sizeof(price));
    memset(stock,0,sizeof(stock));

    for(int i=0;i<n;i++)
    {
        int num,id;
        cin>>num;
        vector<int> tmp;
        if(num)//for those non-retailers push back their retailers or distrubutor
            while(num--)
            {
                cin>>id;
                tmp.push_back(id);
            }
        else//for those retailers, push back -1 to indicate it's a retailer,and update stock;
        {
            double st;
            cin>>st;
            stock[i]=st;
            tmp.push_back(-1);
        }
        chain.push_back(tmp);
    }
    double sum=0;

    updatePrice(0,rootPrice);
    for(int i=0;i<n;i++)
    {
        sum += price[i]*stock[i];   
    }
    printf("%.1f\n",sum);
    return 0;
}