问题描述:

给出一个有向无环的连通图,起点为$1$终点为$N$,每条边都有一个长度。绿豆蛙从起点出发,走向终点。

到达每一个顶点时,如果有$K$条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 $1/K$ 。

现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

输入:

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

输出:

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

思路:

这个的期望按照套路应该反着求,所以我们反向建边,从终点开始进行概率DP。对于DAG上的DP当然要基于拓扑排序啦,然后DP之类的都很简单,看代码就好了。

代码:

#include <bits/stdc++.h>
#define MAXN 200005
#define LL long long
using namespace std;

int n, m, cnt, head[MAXN], deg[MAXN],temp[MAXN];
double dis[MAXN];

struct Edge {int next, to, dis;} edge[MAXN];

void addedge(int from, int to, int dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].dis=dis;
    deg[to]++;
    head[from]=cnt;
}


void topsort()
{
    queue<int> q;
    q.push(n);
    while(!q.empty())
    {
        int tot=0;
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            dis[to]+=(dis[x]+edge[i].dis)/temp[to];
            //printf("%d %d %lf %lf!!!\n", x, to, temp[to], dis[to]);
            if(deg[to]<=0) continue;
            deg[to]--;
            if(!deg[to]) q.push(to);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(y, x, z);
    }
    memcpy(temp, deg, sizeof(deg));
    topsort();
    printf("%.2lf\n", dis[1]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注