首页 > 代码库 > BZOJ3036: 绿豆蛙的归宿&Wikioi2488:绿豆蛙的归宿
BZOJ3036: 绿豆蛙的归宿&Wikioi2488:绿豆蛙的归宿
3036: 绿豆蛙的归宿
Time Limit: 2 Sec Memory Limit: 128 MBSubmit: 108 Solved: 73
[Submit][Status]
Description
随着新版百度空间的下线,Blog宠物绿豆蛙完成了它的使命,去寻找它新的归宿。
给出一个有向无环的连通图,起点为1终点为N,每条边都有一个长度。绿豆蛙从起点出发,走向终点。
到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?
Input
第一行: 两个整数 N M,代表图中有N个点、M条边
第二行到第 1+M 行: 每行3个整数 a b c,代表从a到b有一条长度为c的有向边
Output
从起点到终点路径总长度的期望值,四舍五入保留两位小数。
Sample Input
4 4
1 2 1
1 3 2
2 3 3
3 4 4
1 2 1
1 3 2
2 3 3
3 4 4
Sample Output
7.00
HINT
对于100%的数据 N<=100000,M<=2*N
Source
Poetize3
题解:
简单的期望DP,要从终点往回推
代码:
View Code
1 {$M 1000000000,0,maxlongint} 2 const maxn=100000+1000; 3 type node=record 4 next,go,w:longint; 5 end; 6 var e:array[0..2*maxn] of node; 7 outp,head:array[0..maxn] of longint; 8 f:array[0..maxn] of double; 9 i,n,m,x,y,z,j,tot:longint;10 procedure insert(x,y,z:longint);11 begin12 inc(tot);13 e[tot].go:=y;e[tot].w:=z;e[tot].next:=head[x];head[x]:=tot;14 end;15 procedure init;16 begin17 readln(n,m);18 for i:=1 to m do19 begin20 readln(x,y,z);insert(x,y,z);inc(outp[x]);21 end;22 end;23 procedure dfs(x:longint);24 var i,y:longint;25 begin26 if f[x]<>-1.0 then exit;27 f[x]:=0.0;28 i:=head[x];29 while i<>0 do30 begin31 y:=e[i].go;32 dfs(y);33 f[x]:=f[x]+f[y]+e[i].w;34 i:=e[i].next;35 end;36 if outp[x]<>0 then f[x]:=f[x]/outp[x];37 end;38 39 procedure main;40 begin41 for i:=1 to n do f[i]:=-1.0;42 dfs(1);43 writeln(f[1]:0:2);44 end;45 begin46 assign(input,‘input.txt‘);assign(output,‘output.txt‘);47 reset(input);rewrite(output);48 init;49 main;50 close(input);close(output);51 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。