与这题非常类似的题目，我用的dfs解的-----Highest Price in Supply Chain

题目


OJ平台

题目翻译

  • 关键句意：

where in the i-th line, Ki is the total number of distributors or retailers who receive products from supplier i, and is then followed by the ID's of these distributors or retailers.
其中，在第i行中，Ki是从供应商i接收产品的分销商或零售商的总数，然后是这些分销商或零售商的ID。(注意i是它们的供应商！)

Kj being 0 means that the j-th member is a retailer, then instead the total amount of the product will be given after Kj.
Kj为0意味着第j个成员是零售商，那么产品的总数量将在Kj之后给出。其实就是为0就代表它没有继续分销，直接开始零售了，接下来给出的就是他所进货的多少了。

代码详解

输入处理

void Input() {
    ios::sync_with_stdio(false);
    cin >> N >> p >> r;
    for (int i = 0; i < N; i++) { /*建树*/
        int t; cin >> t;
        if (t)
            while (t--) {
                int n; cin >> n; //更新它的子节点
                node[i].emplace_back(n);
            }
        else { //记录结束的结点(零售商)以及它的购买数量
            int n ; cin >> n;
            mp.emplace_back(make_pair(i, n));
        }
    }
}

输出处理

先用bfs进行一次层序更新一下对应结点的增长率！再进行答案的更新。

void bfs() {
    Q.push(0); //利用bfs得出层级更新利率rr
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (auto && t : node[x]) {
            rr[t] = rr[x] + rr[x] * (r / 100.0);
            Q.push(t);
        }
    }
}
void print() {
    bfs();
    double res = 0;
    for (auto && t : mp) {
        res += rr[t.first] * (double)t.second * p;
    }
    cout << fixed << setprecision(1) << res;
}

汇总代码提交

效率不错！

#include<bits/stdc++.h>
using namespace std;
#define MaxN 100001
int N;
double p, r;
vector<int> node[MaxN];
queue<int> Q;

//这道题仍然是以0为根节点，而结束的结点它也告诉你了，在个数为0的时候作结束。
//在结点为0的时候，它最终给出它的大小(就是这条线得到的商品数量)，而销售额就是商品数量*商品价格*增长率
vector<pair<int, int>>mp;
vector<double>rr(MaxN, 1); //存储每个结点得到的增长利润
void Input() {
    ios::sync_with_stdio(false);
    cin >> N >> p >> r;
    for (int i = 0; i < N; i++) { /*建树*/
        int t; cin >> t;
        if (t)
            while (t--) {
                int n; cin >> n; //更新它的子节点
                node[i].emplace_back(n);
            }
        else { //记录结束的结点以及它的购买数量
            int n ; cin >> n;
            mp.emplace_back(make_pair(i, n));
        }
    }
}

void bfs() {
    Q.push(0); //利用bfs得出层级更新利率rr
    while (!Q.empty()) {
        int x = Q.front(); Q.pop();
        for (auto && t : node[x]) {
            rr[t] = rr[x] + rr[x] * (r / 100.0);
            Q.push(t);
        }
    }
}
void print() {
    bfs();
    double res = 0;
    for (auto && t : mp) {
        res += rr[t.first] * (double)t.second * p;
    }
    cout << fixed << setprecision(1) << res;
}
int main() {
    Input();
    print();
    return 0;
}