1065. [Nescafe19] 绿豆蛙的归宿
★ 输入文件:ldfrog.in
输出文件:ldfrog.out
简单对比
时间限制:1 s 内存限制:128 MB
【背景】
随着新版百度空间的下线,Blog宠物绿豆蛙完成了它的使命,去寻找它新的归宿。
【题目描述】
给出一个有向无环的连通图,起点为1终点为N,每条边都有一个长度。绿豆蛙从起点出发,走向终点。
到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?
【输入格式】
第一行: 两个整数 N M,代表图中有N个点、M条边
第二行到第 1+M 行: 每行3个整数 a b c,代表从a到b有一条长度为c的有向边
【输出格式】
从起点到终点路径总长度的期望值,四舍五入保留两位小数。
【输入样例】
4 4
1 2 1
1 3 2
2 3 3
3 4 4
【输出样例】
7.00
【时限】
各个测试点1s
【数据范围】
对于20%的数据 N<=100
对于40%的数据 N<=1000
对于60%的数据 N<=10000
对于100%的数据 N<=100000,M<=2*N
/* 期望=概率*贡献. 然后把贡献停留在点上最后累加. */ #include<cstdio> using namespace std; const int N=1e5+5; struct edge{int v,w,next;}e[N<<1];int tot,head[N]; int m,n,out[N]; double s[N],ans[N],res; void add(int x,int y,int z){ e[++tot].v=y; e[tot].w=z; e[tot].next=head[x]; head[x]=tot; } void dp(int x){ for(int i=head[x];i;i=e[i].next){ int v=e[i].v; s[v]=s[x]/out[x]; dp(v); ans[x]+=s[v]*e[i].w; } } int main(){ freopen("ldfrog.in","r",stdin); freopen("ldfrog.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z);out[x]++; } s[1]=1; dp(1); for(int i=1;i<=n;i++) res+=ans[i]; printf("%.2lf",res); return 0; }