A1090-Highest Price in Supply Chain

注意DFS的判定条件

if(depth>maxDepth)
        {
            maxDepth=depth;
            num=1;
        }
        else if(depth==maxDepth) //有可能小于之前的深度
            num++;
        return;
#include<bits/stdc++.h>
using namespace std;
int N;
double p,r;
vector<int> child[100010];
int maxDepth=-1,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()
{
    scanf("%d %lf %lf",&N,&p,&r);
    int supply,root;
    for(int n=0;n<N;n++)
    {
        scanf("%d",&supply);
        if(supply!=-1)
            child[supply].push_back(n);
        else
            root=n;
    }
    DFS(root,0);
    printf("%.2f %d\n",p*pow(1+r/100,maxDepth),num);
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容