code[vs] 2488 绿豆蛙的归宿【反向拓扑+DP】

题目：

给出一个有向无环图，起点为1终点为N，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。绿豆蛙从起点出发，走向终点。
到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。
现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

样例输入

样例输出

7.00

分析：

先在草稿纸上构图（样例的），再看，此题基本就是用DP来解决了，但我们又联想起DP模板题中有“最短路径”一题，想起那个题既可以正序算又可以逆序算，那么，这个题也都可以吗？

显然是不能顺序的

1====>2

= =

= /

= > 3 ===>4

因为牵扯到概率，那么我们可以发现，从2到3的概率与1到2概率有关，因此2到3的路径长度同时需要乘以1到2的概率和2到3的概率，而如果用DP的话，一般只讨论该状态与前一个状态的关系，如果每一条路都要考虑以前所有路的概率，是很难实现的。

因此我们考虑倒序，显然，从1到2概率与2到3的概率无关，因此我们可以大胆地用1到2的路径加上2到终点的数学期望再乘以从1选择走2的概率，算出1到终点的数学期望。

这里还要借鉴一点拓扑排序的思想，倒序从第一个没有后继的点开始，一一沿着和它相连的边访问相邻节点，并且每访问一个，就删去该边，直到把他的边删完为止。接下来寻找下一个没有后继的点，再来一遍……

下面是参考代码：

#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
struct edge
{
    int to;
    double len;
}l[200010];
int c1[100010]={0},pc1[100010]={0};
int exist[100010]={0},nxt[200010]={0};
double dp[100010]={0}; 
int N,M;//N个点，M条边 
int tot=0;
int a,b,d;
void build(int x,int y,int dd)
{
    l[++tot].to=y;
    l[tot].len=dd;
    nxt[tot]=exist[x];
    exist[x]=tot;
}
stack<int> q;
void topo_DP()
{
    for(int i=1;i<=N;i++)
        if(c1[i]==0)
            q.push(i);
    while(!q.empty())
    {
        int t=q.top();
        q.pop();
        for(int i=exist[t];i;i=nxt[i])//其实是在边与边之间建立了关系，循环遍历边即可 
        {
            int v=l[i].to;
            int u=t;
            dp[v]=(double)(dp[v]+(dp[u]+l[i].len)/c1[v]);
            //如果将所有由v延伸出来的边都遍历完了，那么下一个遍历起点就是v,倒序遍历 
            --pc1[v];
            if(!pc1[v]) 
                q.push(v);
        }
    }
}

int main()
{
    cin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        cin>>a>>b>>d;
        build(b,a,d);//直接反向建图，前驱变为后继；
        c1[a]++;
        pc1[a]++;    
    } 
    topo_DP();
    printf("%.2f",dp[1]);
    return 0;
}

View Code