pat 1090 highest price in supply chain

Note:

这里面用了树的先根遍历算法和层序遍历算法,很经典的。常练! ## pow函数的用法 ## 还有是当题目要求对结果进行格式化的时候,最好使用printf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 100010
using namespace std;
struct node
{
int layer;
vector<int> child;
}Node[MAX];
int cnt = 0;
void preOrder(int root , int layer)
{
if(Node[root].layer == layer)
{
++cnt;
}
for(int i = 0 ; i < Node[root].child.size() ; ++i)
{
preOrder(Node[root].child[i] , layer);
}
}
int layerOrder(int root)
{
queue<int> q;
int front = 0 , last=1 , rear = 0 , layer = 0;
q.push(root);
Node[root].layer = 0;
++rear;
while(!q.empty())
{
int now = q.front();
q.pop();
++front;
for(int i = 0 ; i < Node[now].child.size(); ++i)
{
int child = Node[now].child[i];
Node[child].layer = Node[now].layer+1;
q.push(child);
++rear;
}
if(front == last)
{
++layer;
last = rear;
}
}
return layer;
}
//另一种解法DFS
/*
当节点index的子节点个数为0时,表示到达了叶子节点,此时,判断当前深度depth是否大于maxDepth,如果是,更新maxDepth并重置cnt为1,如果不是,判断depth是否等于maxDepth,如果是,令cnt++,表示最大深度的节点个数+1
*/
int maxDepth = 0;
void DFS(int index , int depth)
{
if(Node[index].child.size == 0)//此时说明到达底部(叶节点)
{
if(depth > maxDepth)
{
maxDepth = depth;
cnt = 1;
}else if(depth == maxDepth)
{
++cnt;
}
return;
}
for(int i = 0 ; i < Node[index].child.size(); ++i)
{
DFS(Node[index].child[i] , depth+1);
}
}
int main()
{
int N;
double p , r;
scanf("%d%lf%lf" , &N , &p , &r);
r = r/100;
int i , father , root;
for(i = 0 ; i < N ; ++i)
{
scanf("%d" , &father);
if(father == -1)
{
root = i;
continue;
}
Node[father].child.push_back(i);
}
int layer = layerOrder(root);
preOrder(root , layer-1);
printf("%.2f %d" , p * pow(1+r , layer-1) , cnt);
return 0;
}

热评文章