1106. Lowest Price in Supply Chain.md

【PAT A-1106】Lowest Price in Supply Chain

题意概述

供应链是零售商、经销商和供应商构成的网络，每个人都参与将产品从供应商转移到客户的过程。从一个根供应商开始，链上的每个人都以价格 P 从一个供应商那里购买产品，然后以比 P 高出 R％的价格出售或分发产品。只有零售商会面向顾客销售。假定供应链中的每个成员除根供应商外都只有一个供应商，并且没有供应周期。给出一条供应链，输出零售商中的最低单价。

输入输出格式

第一行包含三个正数：N、P、R，分别表示供应链中成员的总数（所有结点的 ID 从 0 到 N-1 编号）、根供应商给出的单价、每个经销商或零售商的价格上涨百分比。第一行包含三个正数：N、P、R，分别表示供应链中成员的总数（所有结点的 ID 从 0 到 N-1 编号，根供应商的 ID 为 0）、根供应商给出的单价、每个经销商或零售商的价格上涨百分比。接下来 N 行，每行输入为ID K ID[1] ID[2] ... ID[K]的格式，其中 ID 的表示非叶结点编号，K 是其儿子结点的数量，接下来的 K 个 ID 表示这 K 个儿子结点编号。如果 K 为 0，表示该结点是一个零售商。

输出零售商中的最低单价和单价为该最低单价的零售商个数，最低单价保留四位小数。

数据规模

$$0<N \le{10}^5$$

使用 DFS 的 C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 1e5 + 5;
vector<vector<gg>> tree(MAX);
vector<double> price(MAX);
gg ni, ki, ai, minNum = 0;
double ri, minPrice = INT_MAX;
void dfs(gg root) {
    if (tree[root].empty()) {
        if (price[root] < minPrice) {
            minPrice = price[root];
            minNum = 1;
        } else if (abs(minPrice - price[root]) < 1e-6) {
            ++minNum;
        }
    }
    for (gg i : tree[root]) {
        price[i] = price[root] * (1 + ri);
        dfs(i);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> ni >> price[0] >> ri;
    ri /= 100;
    for (gg i = 0; i < ni; ++i) {
        cin >> ki;
        while (ki--) {
            cin >> ai;
            tree[i].push_back(ai);
        }
    }
    dfs(0);
    cout << fixed << setprecision(4) << minPrice << " " << minNum;
    return 0;
}

使用 BFS 的 C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 1e5 + 5;
vector<vector<gg>> tree(MAX);
vector<double> price(MAX);
gg ni, ki, ai, minNum = 0;
double ri, minPrice = INT_MAX;
void bfs(gg root) {
    queue<gg> q;
    q.push(root);
    while (not q.empty()) {
        auto t = q.front();
        q.pop();
        if (tree[t].empty()) {
            if (price[t] < minPrice) {
                minPrice = price[t];
                minNum = 1;
            } else if (abs(minPrice - price[t]) < 1e-6) {
                ++minNum;
            }
        }
        for (auto i : tree[t]) {
            q.push(i);
            price[i] = price[t] * (1 + ri);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> ni >> price[0] >> ri;
    ri /= 100;
    for (gg i = 0; i < ni; ++i) {
        cin >> ki;
        while (ki--) {
            cin >> ai;
            tree[i].push_back(ai);
        }
    }
    bfs(0);
    cout << fixed << setprecision(4) << minPrice << " " << minNum;
    return 0;
}