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.

用另一个场景来理解, 题目是这么个意思, 给你一棵树, 想象从树的根root节点灌水, 一开始根的水的流量是p, 然后每次从水流从一个父亲节点流向孩子节点, 水流就被放大到原来的(1 + r)倍, 每个叶子节点给出特殊的和r无关的系数, 水流流向叶子的时候被放大成Li倍, Li对于每个叶子来讲不同, 求所有叶子的水流总和.

1079. Total Sales of Supply Chain 算法分析:

深度优先搜索一下, 遍历每个节点的同时计算出每个节点的”水流量”, 最后累加, 没什么特殊的, AC代码如下:

#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