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

题意翻译

「Poetize3」

题目背景

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

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：复制

输出样例#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 = , INF = 1e9 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, M;

struct Edge {

    int u, v, w, nxt;

}E[MAXN];

int head[MAXN], num = ;

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 = ; i <= N; i++)

        if(inder[i] == )

            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, -, sizeof(head));

    N = read(); M = read();

    for(int i = ; 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[]);

    return ;

}

秒客网