首页 > 代码库 > 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 }
2488 绿豆蛙的归宿
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。