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 }