bzoj_3036 绿豆蛙的归宿

题目:

  随着新版百度空间的下线,Blog宠物绿豆蛙完成了它的使命,去寻找它新的归宿。
  给出一个有向无环的连通图,起点为1终点为N,每条边都有一个长度。绿豆蛙从起点出发,走向终点。
  到达每一个顶点时,如果有K条离开该点的道路,绿豆蛙可以选择任意一条道路离开该点,并且走向每条路的概率为 1/K 。
  现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?

思路:

  设点到的期望长度,根据全期望公式可得(为从出发的边的集合):
  
  所以只要把所有点按拓扑序排序,就能直接跑dp了。

代码:

#include <bits/stdc++.h>
#define MAXN 100003
using namespace std;
int n,m,ind[MAXN],outd[MAXN];
struct Edge{
    int w,to;
};
vector<Edge> mp[MAXN];
int q[MAXN];
void topo(){
    int hed=1,tai=1;
    q[tai++]=1;
    while(hed<tai){
        int o=q[hed++];
        for(int i=0;i<mp[o].size();i++){
            Edge e=mp[o][i];
            if(--ind[e.to]==0)
                q[tai++]=e.to;
        }
    }
}
double dp[MAXN];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,v;i<=m;i++){
        scanf("%d%d%d",&a,&b,&v);
        mp[a].push_back((Edge){v,b});
        ind[b]++;outd[a]++;
    }
    topo();
    for(int i=n;i;i--){
        int o=q[i];
        for(int j=0;j<mp[o].size();j++){
            Edge e=mp[o][j];
            dp[o]+=(dp[e.to]+e.w)/outd[o];
        }
    }
    printf("%.2lf",dp[1]);
    return 0;
}