PAT甲级 1079（C++）

PAT甲级 1079（C++）

测试点2、3、5没过问题：网上调查之后发现，用float计算结果精度不够，改成double就好了

测试点6一开始超时了，当时代码：

#include
#include
#include
using namespace std;
vectorfather;
vector  is_retailer;
int times;double sum;
double price, rate;
void dps(int end,int now) {
	if (father[now] == -1) {
		sum += is_retailer[end] * price * pow(1 + rate / 100, times);
		return;
	}
	times++;
	dps(end, father[now]);
}
int main() {
	int N; cin >> N;
	cin >> price >> rate;
	father.resize(N,-1);
	is_retailer.resize(N,-1);
	for (int i = 0; i < N; i++) {
		int number; cin >> number;
		for (int j = 1; j <= number; j++) {
			int child; cin >> child;
			father[child] = i;
		}
		if (number == 0) cin >> is_retailer[i];
	}
	sum = 0;
	for (int i = 0; i < N; i++) {
		if (is_retailer[i] != -1) {
			times = 0;
			dps(i, i);
		}
	}
	printf("%.1lf", sum);
	return 0;
}

然后稍微看了一下这个链接的思路：PAT甲级1079_湛蓝的天空-CSDN博客

AC代码如下：

#include
#include
#include
using namespace std;
vectorchildren;
vector  is_retailer;
vectorlayer;
double sum,price, rate;
void update(int father) {
	if(children[father]==-1) return;
	layer[children[father]] = layer[father] + 1;
	update(children[father]);
}
int main() {
	int N; cin >> N;
	cin >> price >> rate;
	children.resize(N,-1);
	is_retailer.resize(N,-1);
	layer.resize(N, 0);
	for (int i = 0; i < N; i++) {
		int number; cin >> number;
		for (int j = 1; j <= number; j++) {
			int child; cin >> child;
			children[i] = child;
			layer[child] = layer[i] + 1;
			update(child);
		}
		if (number == 0) cin >> is_retailer[i];
	}
	sum = 0;
	for (int i = 0; i < N; i++) {
		if (is_retailer[i] != -1) 
			sum += is_retailer[i] * price * pow(1 + rate / 100, layer[i]);
	}
	printf("%.1lf", sum);
	return 0;
}

相比改之前的代码，dps更新层数走过的路径更短，而改之前要把所有路走到头。