题目描述
树状销售图(因为零售商只有一个,根节点唯一)
求到叶结点最短路的个数和长度
剪枝,用d[u]存,避免了同一父母的叶子节点的计算
dfs思路
- 子问题:根的高度是0(边界,没有子问题了),他的孩子(数组存父子关系),高度+1
) $O(n^logn)$
pow(底数,幂次)
pow(2,10)=1024
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<unordered_map>
#include<set>
#include<cctype>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N = 1e5+10;
int f[N],d[N];
bool is_leaf[N];
int dfs(int u)
{
if(d[u]!=-1) return d[u];//f[u]之前递归遍历时,赋好值了
if(u==0) return d[u]=0;
// if (f[u] == -1) return d[u] = 0;
return d[u]=dfs(f[u])+1;
}
int main()
{
freopen("1.txt","r",stdin);
int n;
double p,r;
scanf("%d %lf %lf",&n,&p,&r);
memset(f,-1,sizeof f);memset(d,-1,sizeof d);
for(int i=0;i<n;i++)
{
int k;scanf("%d",&k);
if(k==0) is_leaf[i]=true;
while(k--)
{
int son;scanf("%d",&son);
f[son]=i;
}
}
int res=N,cnt=0;
for(int i=0;i<n;i++)
{
if(is_leaf[i])
{
if(res>dfs(i)) res=dfs(i),cnt=1;
else if(res==dfs(i)) cnt++;
// cout<<dfs(i)<<endl;
}
}
//cout<<res<<endl<<cnt;
printf("%.4lf %d\n",p*pow(1+r/100,res),cnt);
return 0;
}
尝试1
24分原因:没用scanf
22分原因:没剪枝 if(d[u]) return d[u];
int dfs(int u)
{
if(d[u]) return d[u];//f[u]之前递归遍历时,赋好值了
if(u==0) return 0;
// if (f[u] == -1) return d[u] = 0;
return d[u]=dfs(f[u])+1;
}
这样写,不赋值-1.也对