题解 P4316 【绿豆蛙的归宿】

· · 题解

妙，妙啊。

这道题让我非常愉悦，一开始做法完全没有思路，后来看了Oven的解析又看了各路大神的题解，本蒟蒻仿佛在黑暗中发现了一盏明灯。他们的代码写的有理有据，题解让人信服、简洁明了……

但我还是看不懂qaq 历经千辛万苦，我发现了一位大佬的代码。他没怎么用拓扑排序，也没用记忆化搜索，最重要的是他给出的求解期望的思路和我们上课时的方法完全一致！所以受他的启发，我终于把这道题A了……

给一个该大佬题解的链接

这道题看起来挺头疼，但它是一个有向无环图（原谅我太弱看到DAG都不知道是什么意思……）。因此一条边顶一下来的期望路径长度是不会改变的！根据期望的线性性，我们可以将这个问题转化为求每一条边经过的长度期望之和。因此我们先把图存下来，然后dfs，dfs里的两个变量分别是dan当前所在的点和期望值。我们从1开始，搜索它出发的每一条边，然后tot++,用期望除以边数，可以得到1/tot为概率，概率再乘上边权，最后求和，就是总期望。然后dfs这条边连的下一个点……以此类推。是不是这样更好理解呢？（至少对于我这么弱的人是的）

直接上代码，存图方式很弱，大佬们不要嘲笑……

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=100010;
const int maxm=200010;
int head[maxn],nnext[maxm];
int to[maxm],length[maxm];
bool b[maxn];
int tot;
int n,m;
double ans=0;
void add(int x,int y,int l)
{
    tot++;
    nnext[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    length[tot]=l;
} 
void dfs(int q,double qw) //q为当前的点，qw为目前的期望值 
{
    int num=0;
    for(int i=head[q];i;i=nnext[i]) 
    {
        num++; // 求出当前所在点连的边数 
    }   
    qw=qw/num; // 加了概率的期望 
    for(int i=head[q];i;i=nnext[i]) 
    {
        ans+=length[i]*qw;
        dfs(to[i],qw); 
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    b[1]=1;
    dfs(1,1);
    printf("%.2lf",ans);
    return 0;
}