题解 P4316 【绿豆蛙的归宿】

题解 P4316 【绿豆蛙的归宿】

题目传送门：

https://www.luogu.org/problemnew/show/P2801

这题是道期望dp经典模型（水积分题）

可能这是我做过的第二道比较正经的期望题了。。。

但是个人感觉。。。好像做的顺序不太对？

这题看完了可以去看看这题：

luogu p1850 换教室

（也是一道期望dp毒瘤题）

=========================================================

上面都是没什么用的。。。下面才是正题

一看这题。。。肯定是个DAG（别问我怎么看出来的QWQ）

根据题目要求，我们很自然的可以想到：

设状态f[x]表示点x到终点n的期望路径总长

显然，要求的答案为f[1],而且有f[n]=0

（终点到自己的期望距离肯定为0啊。。。）

发现这时就是期望dp的套路了。。。

正好要将期望dp，不妨我们先来说说期望dp的具体sao操作

期望dp，也加概率dp

一般来说，期望dp找到正确的状态后，转移是比较容易想到的。

但一般情况下，状态一定是“可数”的

事实上，将问题直接作为dp的状态是最好的。

如，问“n人做XX事的期望次数”，那么不妨设计状态为f[i]表示i个人做完事的期望。

转移一般是递推，通常分两种，一种是从上一个状态转移得（填表法），另一种是转移向下一个状态（刷表法）。

有时期望dp需以最终状态为初始状态转移，即逆推。

如f[i]表示期望还要走f[i]步到达终点。这种状态的转移是刷表法

形如f[i]=∑p[i→j]*f[j]+w[i→j]，其中p表示转移的概率，w表示转移对答案的贡献。

一般来说，初始状态确定时可用顺推，终止状态确定时可用逆推。

大概期望dp的套路就是这样了吧。。。（我还是菜讲得不太好）

现在我们回到本题

上面提到了，我们设状态f[x]表示点x到终点n的期望路径总长，那么显然有f[n]=0

那么这正好符合了“终止状态确定时可用逆推”的策略套路

具体来说：

对于一条有向边,我们假设它由 x->y

那么有f[x]=(\dfrac{1}{degree[x]})*∑f[y]+w[x->y]

其中degree[x]表示x点的度（结合一下上面给出的式子你就懂了）

仔细观察题目其实你会发现, (\dfrac{1}{degree[x]})其实就是概率(p)

同时又有一个问题，那就是转移时的过程怎么实现

不妨这样想：既然是个DAG，那么我们可以“倒过来”想

具体来讲，我们反向连边，进行一遍拓扑排序，在拓扑排序的时候进行期望dp的转移

这时候要注意上面的x和y要反过来（因为我们反向连边了）

那么我们转移方程就设计完啦

（其实还是挺好理解的是不是）（逃

分析一下复杂度

dp转移是与拓扑排序有关的，每次计算几乎是O(1)的

那么时间复杂度瓶颈就是拓扑排序，故时间复杂度为O(n+m)

下面放代码吧

PS：代码里也有解释

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
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*10+c-'0';c=getchar();}
    return f*p;}
const int maxn=100003;
const int maxm=200003;
struct Edge
{
    int from,to,w;
}p[maxm];
int n,m,cnt,head[maxm],in[maxn],dg[maxn];
double f[maxn];//f[x]表示x点到终点n的期望路径总长 
inline void add_edge(int x,int y,int W)//加边
{
    cnt++;
    p[cnt].from=head[x];
    head[x]=cnt;
    p[cnt].to=y;
    p[cnt].w=W;
}
inline void toposort()//拓扑排序
{
    queue <int> q;
    q.push(n);
    while(!q.empty())
        {
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=p[i].from)
                {
                    int y=p[i].to;
                    f[y]+=(f[x]+p[i].w)/dg[y];//dp转移 
                    if(!(--in[y]))q.push(y);
                }
        }
}
int main()
{
    /*这是我做这题的时候写的QAQ
    分析:不妨设f[x]表示x点到终点的期望路径总长度
    显然有f[n]=0
    那么对于一条有向边,连接着x和y点(x->y)
    那么显然有f[x]=sigma(f[y]+w[i])/degree[x] 
    其中degree[x]表示x点的出度,w[i]表示这条边的边权 
    那么假设我们已经知道了f[y]
    我们就可以反推f[x]
    显然只需要反向建边之后跑个拓扑排序就行了
    那么最后答案即为f[1]
    时间复杂度O(n+m) 
    */
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        {
            int x=read(),y=read(),w=read();
            add_edge(y,x,w);//反向建图 
            in[x]++,dg[x]++;
        }
    toposort();
    printf("%.2lf\n",f[1]);
    return 0;
}

这题就算讲完了吧。。。

本人思维比较跳跃，可能写的不是太好，请见谅

感谢你的阅读！

最后无耻的推一波我的blog：

https://www.luogu.org/blog/new2zy/

拜拜~~~