[PAT-A 1090]Highest Price in Supply Chain

考察樹的周遊

• List item

題目大意：

題目大意：給出一顆銷售供應的樹，樹根唯一，在樹根處的貨物價格為P，然後從根節點開始每往孩子節點走一層，該層的貨物價格會在父親的價格節點上增加r%,求所有葉節點中的最高價格以及這個價格的葉節點的個數。

思路：

1.每一層的價格都在上一層的基礎上*（1+r%）,隻需要計算深度最深的節點即可。

2.使用vector<int> child[maxv]來存儲樹，使用DFS或BFS得到最大深度

3.全局變量中使用maxDepth來表示最大深度，使用num表示最大深度葉節點的個數，初值為0

sample input中 第二行

1 5 4 4 -1 4 5 3 6
           

S[i]表示 S[i]是i的Supplier 即S[i]是i的父親節點

AC代碼

//PAT_A 1090
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 100010;
vector<int> child[maxn];
double p, r;
int n, maxDepth = 0, num = 0;
void dfs(int index, int depth) {
	if (child[index].size() == 0) {
		if (depth > maxDepth) {
			maxDepth = depth;
			num = 1;
		}
		else if (depth == maxDepth)num++;
		return;
	}
	for (int i = 0; i < child[index].size(); i++) {
		dfs(child[index][i], depth + 1);
	}
}
int main() {
	int father, root;
	(void)scanf("%d %lf %lf", &n, &p, &r);
	r /= 100;
	for (int i = 0; i < n; i++) {
		(void)scanf("%d", &father);
		if (father != -1) {
			child[father].push_back(i);
		}
		else root = i;
	}
	dfs(root, 0);
	printf("%.2f %d\n", p * pow(1 + r, maxDepth), num);
	return 0;
}