A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3036 绿豆蛙的归宿 概率期望dp
发表于: | 分类: Oi | 评论:0 | 阅读:62

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

套路题目,用 $f(i)$ 表示 $i$ 到 $N$ 的期望长度
$$f(i) = \frac{\sum\limits_{i\to j}{f(j)+val_{i\to j}}}{deg_i},f(N)=0$$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 100000+5;
const int M = N << 1;
using namespace std;

int deg[N];
int head[N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct graph
{
    int next,to,val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

inline void add(int x,int y,int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z);
    head[x] = cnt; deg[x] ++;
}

bool vis[N];
double F[N];

void DFS(int x)
{
    if(vis[x]) return; vis[x] ++;
    for(int i=head[x];i;i=edge[i].next)
        DFS(edge[i].to),F[x] += F[edge[i].to] + edge[i].val;
    if(deg[x]) F[x] = F[x] / deg[x];
}


int main()
{
    int n = read(), m = read(),x,y,z;
    for(int i=1;i<=m;++i) {
        x = read(), y = read(), z = read();
        add(x,y,z);
    }
    DFS(1); printf("%.2lf\n",F[1]);
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP