# PAT 解题报告 1079. Total Sales of Supply Chain (25)

### 1079. Total Sales of Supply Chain 题目描述：

A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）– everyone involved in moving a product from supplier to customer.

Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. Only the retailers will face the customers. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.

Now given a supply chain, you are supposed to tell the total sales from all the retailers.

### 1079. Total Sales of Supply Chain 算法分析：

```#include <iostream>
#include <cstdio>
#include <vector>

double dfs(int node, double parentPrice, double r,
const std::vector<std::vector<int> > &graph,
const std::vector<int> &nProduct) {
double myPrice;
if(0 == node)
myPrice = parentPrice;
else
myPrice = (1.0 + r / 100.0) * parentPrice;

if(graph[node].empty())
return myPrice * nProduct[node];

double ret = 0.0;
for(int i = 0; i < graph[node].size(); ++i) {
ret += dfs(graph[node][i], myPrice, r, graph, nProduct);
}
return ret;
}

int main() {
int n = 0;
double p = 0.0;
double r = 0.0;

std::cin >> n >> p >> r;

std::vector< std::vector<int> > graph(n);
std::vector<int>  nProduct(n, 0);

int ki;
for(int i = 0; i < n; ++i) {
std::cin >> ki;
if(0 == ki) {
std::cin >> nProduct[i];
}
else {
graph[i].resize(ki);
for(int j = 0; j < ki; ++j)
std::cin >> graph[i][j];
}
}
printf("%.1lf\n", dfs(0, p, r, graph, nProduct));
return 0;
}
```

### 1079. Total Sales of Supply Chain 注意点：

DFS可能比较慢, 时间上用了100ms. 也可以采用BFS, 应该会快一些.

Written on April 22, 2014