题解 P4316 【绿豆蛙的归宿】

· · 题解

一道关于期望的大水题

据说面向数据编程更有助于AC（不是)

显然，选择从u到v这条边的概率是 1/出度[u] （k就是出度）

那么从1到n一条路径总长度期望就是 路径总长度 * 经过每条边的概率

所以，最后只要遍历所有1到n的路径把答案累加就好啦

样例

其实我好像是从样例发现的式子

(2+4) (1/2) + (1+3+4) (1/2）=7

然后就变成了裸的dfs？？?

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=100000+5;
const int maxm=200000+5;

int cnt,n,m,u,v,w;

int first[maxn],outdeg[maxn];

double ans;

struct Edge
{
    int to,dis,nxt;
}a[maxm];

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

inline void addedge(int from,int to,int dis)
{
    a[++cnt]=(Edge){to,dis,first[from]};
    first[from]=cnt;
}

inline void dfs(int u,double p,int sum)
{
    if(u==n)
    {
        ans=(double)ans+p*sum;
        return;
    }
    for(int i=first[u];i;i=a[i].nxt)
    {
        int v=a[i].to;
        dfs(v,(double)1/outdeg[u]*p,sum+a[i].dis);
    }
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read(),w=read();
        outdeg[u]++;
        addedge(u,v,w);
    }
    dfs(1,1,0);
    printf("%.2lf",ans);
    return 0;
}

完结撒fa~