首页 > 其他 > 详细

寻找宝藏

时间:2018-03-27 16:16:13      阅读:268      评论:0      收藏:0      [点我收藏+]

题目描述 
有一棵多叉树T,你在树根处,宝藏在某一叶子节点L。现在你沿着树枝向叶子方向走去,从不回头,如果遇到树叉节点,你等概率地挑选一个分支继续走。请问,在给定T,L的情况下,你有多大概率拿到宝藏?

输入格式 
第一行,整数N,M,L(1< N< 1000,0< M< 1000,0< L< N),分别代表树T上的节点数、树枝的个数,宝藏所在节点。树根为0号结点。 
然后有M行,每行两个整数A,B(0≤ A,B< N)代表从节点A到节点B有一条树枝。可以假设节点A总是更靠近树根。

输出格式 
所求的概率,输出四舍五入到6位小数,然后换行。

输入样例 
6 5 5 
0 1 
1 3 
0 2 
2 4 
2 5 
输出样例 
0.250000

#include <stdio.h>  
#define MAXN 1005  

int father[MAXN] = { -1 }, son[MAXN] = { 0 };

main()
{
    int l, b, tar, x, y;
    double revp = 1;
    scanf("%d%d%d", &l, &b, &tar);
    while (b--) {
        scanf("%d%d", &x, &y);
        son[x]++; 
        father[y] = x;
    }
    while (father[tar] != -1) {
        tar = father[tar];
        revp *= son[tar];
    }
    printf("%lf\n", 1 / revp);
    return 0;
}

 

寻找宝藏

原文:https://www.cnblogs.com/xym4869/p/8657734.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!