洛谷P4316 绿豆蛙的归宿(期望)

题意翻译

「Poetize3」

题目背景

随着新版百度空间的上线,Blog宠物绿豆蛙完成了它的使命,去寻找它新的归宿。

题目描述

给出一个有向无环图,起点为1终点为N,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。绿豆蛙从起点出发,走向终点。 到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。 现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

输入输出格式

输入格式:

第一行: 两个整数 N M,代表图中有N个点、M条边 第二行到第 1+M 行: 每行3个整数 a b c,代表从a到b有一条长度为c的有向边

输出格式:

从起点到终点路径总长度的期望值,四舍五入保留两位小数。

输入输出样例

输入样例#1: 复制

4 4 
1 2 1 
1 3 2 
2 3 3 
3 4 4

输出样例#1: 复制

7.00

说明

对于20%的数据 N<=100

对于40%的数据 N<=1000

对于60%的数据 N<=10000

对于100%的数据 N<=100000,M<=2*N

直接利用期望的定义推就行。

不过正着推非常不好写

我是建反图推的

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define LL long long 
using namespace std;
const int MAXN = 200000, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
struct Edge {
    int u, v, w, nxt;
}E[MAXN];
int head[MAXN], num = 1;
inline void AddEdge(int x, int y, int z)  {
    E[num] = (Edge) {x, y, z, head[x]};
    head[x] = num++;
}
double inder[MAXN], dis[MAXN], inder2[MAXN];
void Topsort() {
    queue<int> q;
    for(int i = 1; i <= N; i++) 
        if(inder[i] == 0)
            q.push(i);
    while(!q.empty()) {
        int p = q.front(); q.pop();
        //if(p != x) dis[p] = dis[p] / inder2[p];
        for(int i = head[p]; ~i; i = E[i].nxt) {
            int to = E[i].v;
            dis[to] += (dis[p] + E[i].w) / inder2[to];
            inder[to]--;
            if(!inder[to]) q.push(to);        
        }
        
        //dis[p] /= inder2[p];
        //printf("%d %lf %lf\n", p, dis[p], inder2[p]);
    }
}
main() { 
#ifdef WIN32
    //freopen("a.in", "r", stdin);
#endif
    memset(head, -1, sizeof(head));
    N = read(); M = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        swap(x, y);
        AddEdge(x, y, z);
        inder[y]++; inder2[y]++;
    }
    Topsort();
    printf("%.2lf", dis[1]);
    return 0;
}   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏爱撒谎的男孩

回溯算法

28130
来自专栏Petrichor的专栏

leetcode: 72. Edit Distance

24810
来自专栏应兆康的专栏

100个Numpy练习【5】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

620100
来自专栏应兆康的专栏

100个Numpy练习【5】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

791120
来自专栏数据结构与算法

2017.10.23解题报告

预计分数:100+60+0=160 实际分数:100+80+0=180 T1 题目描述 现在有一个字符串,每个字母出现的次数均为偶数。接下来我们把第一次出现的字...

33850
来自专栏苦逼的码农

从零打卡leetcode之day 3--最大子序列

看到三个for循环,时间复杂度的O(n3)。这速度,实在是太慢了。我们来优化优化。

7410
来自专栏数据结构与算法

BZOJ2216: [Poi2011]Lightning Conductor(DP 决策单调性)

首先把给出的式子移项,我们要求的$P_i = max(a_j + \sqrt{|i - j|}) - a_i$。

15920
来自专栏chenjx85的技术专栏

leetcode-40-组合总和 II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

14210
来自专栏小樱的经验随笔

回溯算法入门及经典案例剖析(初学者必备宝典)

前言 基于有需必写的原则,并且当前这个目录下的文章数量为0(都是因为我懒QAQ),作为开局第一篇文章,为初学者的入门文章,自然要把该说明的东西说明清楚,于是。。...

45340
来自专栏深度学习那些事儿

pytorch新手需要注意的隐晦操作Tensor,max,gather

先看官方的介绍: 如果input是一个n维的tensor,size为 (x0,x1…,xi−1,xi,xi+1,…,xn−1),dim为i,然后index必须...

1.5K80

扫码关注云+社区

领取腾讯云代金券