首页 > 其他 > 详细

[题解] [LuoguP4316] 绿豆蛙的归宿

时间:2020-02-22 12:58:32      阅读:45      评论:0      收藏:0      [点我收藏+]

[题解] [LuoguP4316] 绿豆蛙的归宿

一.前言

? 今天本着停课不停学的决心,看了看数学期望。结果是 见不熟悉之数学起身慌而走之。话虽然这么说,但是例题还是要做的,题解也是要写的。凭本人小学水平数学,粗略的理解数学期望就是操作的足够多了之后趋于平均的一个?的东西。,嘛,就相当于骰子扔多了平均值就会趋于一个常数,但是怎么都不会扔出7就对了。(此处为古贺朋绘酱默哀qwq,永远都做不出自己想要的梦我永远喜欢古贺朋绘

二.题意简述

? 说了一个大点的废话以后,进入这一篇的正题。

? 题意:在一个有向无环图中,给出各边的信息,求从起点走到终点的路径长度期望。(顺带一提选择每条边的概率是一样的)

三.思路

? 那么知道了题意之后,很明显的这是个DP。(别问我怎么看出来的问就无效性),那么我们设置 从 i 点到终点的路径长度期望为 \(f[i]\) ,当前 i 的出度为 \(out[i]\) ,选中的边所对的点为 v ,边的长度为 \(dis(i,v)\),就可以得出递推式。
\[ f[i]=\frac{\sum (f[v]+dis(i,v))}{out[i]} \]
ε=(′ο`*)))为什么是这样呢?首先为了平均要除以一个出度是没有问题的(毕竟从终点往前推,同时这里实现的时候可以用分配律搞搞),然后由于是路径长所以是加而不是乘。(不知道这样讲能不能看懂),然后边界条件是 \(f[n]=0\).(显然)

? 虽然说起来是DP,但是实际的应用是DFS,毕竟在图上又要遍历,之类的。

四.CODE

const int MAXN=200005;
int n,m;
int head[MAXN],ne[MAXN],to[MAXN],dis[MAXN],tot,out[MAXN];
inline void add(int x,int y,int z){
    to[++tot]=y;
    ne[tot]=head[x];
    head[x]=tot;
    dis[tot]=z;
}
double f[MAXN];
bool vis[MAXN];
void dfs(int x){
    if(x==n){
        f[x]=0;
        return ;
    }
    if(vis[x])return;
    vis[x]=1;
    for(int i=head[x];i;i=ne[i]){
        int v=to[i];
        dfs(v);
        f[x]+=(f[v]+1.0*dis[i])/out[x];
    }
}
int main(){
n=read();m=read();
m_for(i,1,m){
    int x=read(),y=read(),z=read();
    add(x,y,z);
    out[x]++;
}
dfs(1);
printf("%.2f",f[1]);
return 0;
}

五.后记

? 其实由于某种奇奇怪怪的原因,好像可以先拓扑一下路径再操作,会快一些(大概)

[题解] [LuoguP4316] 绿豆蛙的归宿

原文:https://www.cnblogs.com/clockwhite/p/12344383.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!