首页 > 代码库 > codevs 2488 绿豆蛙的归宿
codevs 2488 绿豆蛙的归宿
2488 绿豆蛙的归宿
http://codevs.cn/problem/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
拓扑排序
#include<cstdio>#include<stack>#define N 100001using namespace std;int front[N],tot;int in[N],out[N];double ans;struct node{ int to,nxt,val; double may;}e[N*2];double f[N];stack<double>s;void add(int u,int v,int w){ e[++tot].to=v; e[tot].nxt=front[u]; front[u]=tot; e[tot].val=w;}int main(){ int n,m; int x,y,z; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); in[y]++; out[x]++; } f[1]=1; s.push(1); int now; while(!s.empty()) { now=s.top(); s.pop(); for(int i=front[now];i;i=e[i].nxt) { f[e[i].to]+=f[now]*1.0/out[now]; e[i].may=f[now]*1.0/out[now]; in[e[i].to]--; if(!in[e[i].to]) s.push(e[i].to); } } for(int i=1;i<=m;i++) ans+=e[i].may*e[i].val; printf("%.2lf",ans);}
codevs 2488 绿豆蛙的归宿
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。