BZOJ3036: 绿豆蛙的归宿

【传送门：BZOJ3036】

---

简要题意：

　　给出一个有向无环图，并且保证每条路径的起点为1，终点为n，且每条边都有权值

　　如果从一个点能到达k个点，那么它将会有1/k的概率走其中一个点

　　求出从起点到终点的期望

---

题解：

　　期望DP，DFS逆推

---

参考代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
double f[110000];
struct node
{
    int x,y,next;double d;
}a[210000];int len,last[110000];
void ins(int x,int y,double d)
{
    len++;
    a[len].x=x;a[len].y=y;a[len].d=d;
    a[len].next=last[x];last[x]=len;
}
int chu[210000];
bool v[110000];
int n;
void dfs(int x)
{
    if(x==n) return ;
    if(v[x]==false) v[x]=true;
    else return ;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        dfs(y);
        f[x]+=f[y]+a[k].d;
    }
    f[x]/=chu[x];
}
int main()
{
    int m;
    scanf("%d%d",&n,&m);
    len=0;memset(last,0,sizeof(last));
    for(int i=1;i<=m;i++)
    {
        int x,y;double d;
        scanf("%d%d%lf",&x,&y,&d);
        ins(x,y,d);chu[x]++;
    }
    memset(v,false,sizeof(v));
    dfs(1);
    printf("%.2lf
",f[1]);
    return 0;
}