专栏首页数据结构与算法2488 绿豆蛙的归宿

2488 绿豆蛙的归宿

2488 绿豆蛙的归宿

时间限制: 1 s

空间限制: 64000 KB

题目等级 : 黄金 Gold

题目描述 Description

  随着新版百度空间的上线,Blog宠物绿豆蛙完成了它的使命,去寻找它新的归宿。

  给出一个有向无环图,起点为1终点为N,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。绿豆蛙从起点出发,走向终点。   到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。   现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

输入描述 Input Description

  第一行: 两个整数 N M,代表图中有N个点、M条边   第二行到第 1+M 行: 每行3个整数 a b c,代表从a到b有一条长度为c的有向边

输出描述 Output Description

  从起点到终点路径总长度的期望值,四舍五入保留两位小数。

样例输入 Sample Input

4 4 1 2 1 1 3 2 2 3 3 3 4 4

样例输出 Sample Output

7.00

数据范围及提示 Data Size & Hint

  对于20%的数据   N<=100   对于40%的数据   N<=1000   对于60%的数据   N<=10000   对于100%的数据  N<=100000,M<=2*N

来源:Nescafe 19

分类标签 Tags 点此展开

感觉跟拓扑排序一点关系都没有啊

数学期望+dfs

期望值:在概率论统计学中,一个离散性随机变量期望值(或数学期望、或均值,亦简称期望,物理学中称为期待值)是试验中每次可能结果的概率乘以其结果的总和。换句话说,期望值是随机试验在同样的机会下重复多次的结果计算出的等同“期望”的平均值。需要注意的是,期望值并不一定等同于常识中的“期望”——“期望值”也许与每一个结果都不相等。(换句话说,期望值是该变量输出值的平均数。期望值并不一定包含于变量的输出值集合里。)

解释一下样例

红色是点权,灰色是累加的ans

注意数据范围,边表+队列实现。

每个点都有一个权值,起点为1,然后当这个点离开拓扑序列时,把权值分解,均分给它指向的点,同时将这个权值乘上边权累加。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=1000001;
 6 const int maxn=0x7fffffff;
 7 struct node
 8 {
 9     int u;
10     int v;
11     double w;
12     int next;
13 }edge[MAXN];
14 int num=1;
15 int head[MAXN];
16 int vis[MAXN];
17 double ans=0;
18 void dfs(int p,double qw)// p 表示正在访问的点    w表示当前的期望值 
19 {
20 //    if(qw>ans)return;
21     int tot=0;
22     for(int i=head[p];i!=-1;i=edge[i].next)
23     {
24         tot++;
25     }
26     qw=qw/tot;
27     for(int i=head[p];i!=-1;i=edge[i].next)
28     {
29         ans=ans+edge[i].w*qw;
30         dfs(edge[i].v,qw);
31     }
32     
33 }
34 int main()
35 {
36     int n,m;
37     scanf("%d%d",&n,&m);
38     for(int i=1;i<=n;i++)head[i]=-1;
39     for(int i=1;i<=m;i++)
40     {
41         scanf("%d%d%lf",&edge[num].u,&edge[num].v,&edge[num].w);
42         edge[num].next=head[edge[num].u];
43         head[edge[num].u]=num++;
44     }
45     vis[1]=1;
46     dfs(1,1);
47     printf("%.2lf",ans);
48     return 0;
49 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P1401 城市(30分,正解网络流)

    题目描述 N( )个城市,M( )条无向边,你要找T( )条从城市1到城市N的路,使得最长的边的长度最小,边不能重复用。 输入输出格式 输入格式: 第1行...

    attack
  • 185. [USACO Oct08] 挖水井

    185. [USACO Oct08] 挖水井 ★★   输入文件:water.in   输出文件:water.out 简单对比 时间限制:1 s   内存限制:...

    attack
  • 3315 时空跳跃者的魔法

    3315 时空跳跃者的魔法 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 白银 Silver 题目描述 Description ...

    attack
  • 集合的前N个元素

    集合的前N个元素:编一个程序,按递增次序生成集合M的最小的N个数,M的定义如下:     (1)数1属于M;     (2)如果X属于M,则Y=2*x+1和Z=...

    attack
  • 令人赞叹的位运算

    想必大家每次阅读第三方源码时,都觉得其中的位运算很酷,让人神往又抓狂。为了搞懂那些操作的具体含义,想去深入了解那些魔法代码背后的原理。

    写代码的阿宗
  • P3376 【模板】网络最大流

    题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。 输入输出格式 输入格式: 第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个...

    attack
  • HDU 1863 畅通工程(Kruskal)

    畅通工程 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K ...

    ShenduCC
  • 二路归并排序简介及其并行化

    归并排序是分治法(Divide and Conquer)的一个典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若...

    Dabelv
  • POJ 1985 Cow Marathon(树的直径)

    Description After hearing about the epidemic of obesity in the USA, Farmer John...

    attack
  • P1339 [USACO09OCT]热浪Heat Wave

    题目描述 The good folks in Texas are having a heatwave this summer. Their Texas Long...

    attack

扫码关注云+社区

领取腾讯云代金券