《算法竞赛进阶指南》0x38概率与数学期望绿豆蛙的归宿

2021-04-19 15:29

阅读：700

标签：front 进阶 can i++ code pre ons 排序建立

题目链接：https://www.acwing.com/problem/content/219/

题目给出一张有向无环图，要求从1到n的路径长度的数学期望，如果一个点有k条出边，那么走每条表的概率都是1/k，我们容易知道，记一个点x到终点n的路径的数学期望是dis[x]，那么dis[x]计算的结果依赖于他所能到达的所有的边，根据这个性质可以发现是跟拓扑排序有关系的，满足这样一种结构：在这个点处理之前它的所有可达的点都已经处理完了。

所以这个问题需要在拓扑排序的同时进行更新操作，需要建立反图，建反图是为了从可达点到该点进行更新。信息的传递是从终点开始的，所以需要建立一张反图进行反向递推。

代码：

#include
#include
#includeusing namespace std;
const int maxn = 100010;
int head[maxn],nxt[maxn*2],ver[maxn*2],len[maxn*2];
int n,m;
int tot=0;
int deg[maxn],out[maxn];
double dis[maxn];//记录点i到n的路径数学期望 
void addedge(int u,int v,int w){
    ver[++tot]=v;
    len[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
int main(){
    cin>>n>>m;
    int u,v,w;
    for(int i=1;i){
        scanf("%d%d%d",&u,&v,&w);
        addedge(v,u,w);//建反图 
        deg[u]++;
        out[u]++;
    }
    queueint> q;
    q.push(n);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            dis[y]+=(dis[x]+(double)len[i])/deg[y];
            if(--out[y]==0)q.push(y);
        }
    }
    printf("%.2lf\n",dis[1]);
}

《算法竞赛进阶指南》0x38概率与数学期望绿豆蛙的归宿

标签：front 进阶 can i++ code pre ons 排序建立

原文地址：https://www.cnblogs.com/randy-lo/p/13288530.html

上一篇：算法-汉诺塔

下一篇：unity-编辑器快捷按键

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：《算法竞赛进阶指南》0x38概率与数学期望绿豆蛙的归宿
文章链接：http://soscw.com/index.php/essay/76721.html

亲，登录后才可以留言！

《算法竞赛进阶指南》0x38概率与数学期望绿豆蛙的归宿

评论

热门文章

推荐文章

最新文章

置顶文章

《算法竞赛进阶指南》0x38概率与数学期望 绿豆蛙的归宿

评论

热门文章

推荐文章

最新文章

置顶文章

《算法竞赛进阶指南》0x38概率与数学期望绿豆蛙的归宿