Description
题目大意：一个供应链有零售商，经营商和供应商，只有零售商和顾客交易，供应商给出价格P，每次往下一层销售价格增长原来的r%倍，问顾客拿到的最低价格以及最低价格零售商的个数
Input
n,P,r k,ki,代表每个节点与k个子节点
Output
最低价格price和零售商个数minnumber
解题思路
算法标签：树的遍历 显然零售商就是叶子节点，我们所找的便是深度最小的叶子节点，以及其个数，最后根据层数算出price,index代表树节点的标号，depth代表搜索树此时的深度，mindepth代表目前找到的叶子节点的最小深度，minnumber代表最小深度叶子节点的个数
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std
;
const int N
= 100005;
const int MAXX
= 1314520;
vector
<int>tree
[N
];
int mindepth
,minnumber
;
void dfs(int index
,int depth
)
{
if(depth
> mindepth
)
return;
if(tree
[index
].size() == 0)
{
if(mindepth
== depth
)
minnumber
++;
else if(mindepth
> depth
)
{
mindepth
= depth
;
minnumber
= 1;
}
}
for(int i
=0;i
< tree
[index
].size();i
++)
dfs(tree
[index
][i
],depth
+1);
}
int main()
{
int n
= 0,k
= 0,id
= 0;
double P
= 0,r
= 0,price
= 0;
cin
>>n
>>P
>>r
;
for(int i
=0;i
<n
;i
++)
{
scanf("%d",&k
);
for(int j
= 0;j
< k
;j
++)
{
scanf("%d",&id
);
tree
[i
].push_back(id
);
}
}
mindepth
= MAXX
;
minnumber
= 1;
dfs(0,0);
price
= P
* pow(1 + r
/100,mindepth
);
printf("%.4lf %d",price
,minnumber
);
return 0;
}
