PAT-ADVANCED1106——Lowest Price in Supply Chain

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805362341822464

题目描述：

题目翻译：

1106 供应链中的最低价格

供应链是零售商，经销商和供应商构成的网络 - 每个人都参与将产品从供应商转移到客户。从一个根供应商开始，链上的每个人都以价格P从一个供应商处购买产品，并以高于P的r％的价格出售或分销它们。只有零售商才会面对客户。 假设供应链中的每个成员除了根供应商之外只有一个供应商，并且没有供应环。现在给定供应链，你需要给出所有零售商中的最低价格。

输入格式：

每个输入文件包含一个测试用例。在每个测试用例中，第一行包含3个正整数：N(<= 10 ^ 5)，供应链中的总节点数（节点编号为0 ~ N - 1，根结点编号为0）；P，代表商品的单位价格；以及r，代表每个经销商或零售商的价格增量百分比。接下来的N行，每行以下述形式描述一个经销商或零售商：

K​i​​ ID[1] ID[2] ... ID[K​i​​]

在第i行，Ki代表的是从供应点i进货的经销商或零售商数量，紧跟着的是这些经销商或零售商的ID。Kj等于0时，表示第j号节点是一个零售商，其后的数字代表该零售商卖出的商品总数。一行中的所有数字以一个空格分隔。

输出格式：

对每个测试用例，输出所有零售商的中的最低价格，结果精确到小数点后4位，以及出售这个价格的零售商数目。两个数字间用一个空格分隔。题目保证这个价格不会超过10 ^ 10。

输入样例：

10 1.80 1.00
3 2 3 5
1 9
1 4
1 7
0
2 6 1
1 8
0
0
0

输出样例：

1.8362 2

知识点：树的广度优先遍历、深度优先遍历

思路一：深度优先遍历的同时记录节点的层级

本题和PAT-ADVANCED1079——Total Sales of Supply Chain、PAT-ADVANCED1090——Highest Price in Supply Chain与PAT-ADVANCED1094——The Largest Generation考察的知识点相同，解法也近乎相同。

时间复杂度和空间复杂度均是O(N)。

C++代码：

#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

struct node{
	vector<int> child;
};

int N;
double P;
double r;
node Node[100000];
int countLevel[100000] = {0};	//第i层有countLevel[i]个叶子节点

void dfs(int nowVisit, int level);

int main(){
	cin >> N >> P >> r;
	int K, ID;
	for(int i = 0; i < N; i++){
		cin >> K;
		if(K != 0){
			for(int j = 0; j < K; j++){
				cin >> ID;
				Node[i].child.push_back(ID);
			}
		}
	}
	dfs(0, 0);
	int minLevel;
	for(int i = 0; i < N; i++){
		if(countLevel[i] != 0){
			minLevel = i;
			break;
		}
	}
	printf("%.4lf %d\n", pow(1 + r / 100, minLevel) * P, countLevel[minLevel]);
}

void dfs(int nowVisit, int level){
	if(Node[nowVisit].child.size() == 0){
		countLevel[level]++;
		return;
	}
	for(int i = 0; i < Node[nowVisit].child.size(); i++){
		dfs(Node[nowVisit].child[i], level + 1);
	}
} 

C++解题报告：

思路二：广度优先遍历的同时为每个节点添加层级信息

时间复杂度和空间复杂度均是O(N)。

C++代码：

#include<iostream>
#include<vector>
#include<cmath>
#include<queue>

using namespace std;

struct node {
	int level;
	vector<int> child;
};

int N;
double P;
double r;
node Node[100000];
int countLevel[100000] = {0};	//第i层有countLevel[i]个叶子节点

void bfs(int nowVisit);

int main() {
	cin >> N >> P >> r;
	int K, ID;
	for(int i = 0; i < N; i++) {
		cin >> K;
		if(K != 0) {
			for(int j = 0; j < K; j++) {
				cin >> ID;
				Node[i].child.push_back(ID);
			}
		}
	}
	bfs(0);
	for(int i = 0; i < N; i++) {
		if(Node[i].child.size() == 0) {
			countLevel[Node[i].level]++;
		}
	}
	int minLevel;
	for(int i = 0; i < N; i++) {
		if(countLevel[i] != 0) {
			minLevel = i;
			break;
		}
	}
	printf("%.4lf %d\n", pow(1 + r / 100, minLevel) * P, countLevel[minLevel]);
}

void bfs(int nowVisit) {
	queue<int> q;
	Node[nowVisit].level = 0;
	q.push(nowVisit);
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(int i = 0; i < Node[now].child.size(); i++){
			Node[Node[now].child[i]].level = Node[now].level + 1;
			q.push(Node[now].child[i]);
		}
	}
}

C++解题报告：