题解 P4316 【绿豆蛙的归宿】

##### 两种方法，正推和逆推 #### 逆推：$dp[i]$表示从$i$到$n$的期望，方程的转移：对于一条从$x$到$y$边 #### $dp[x]=\sum\limits_{i=1}^{oud[x]}(dp[y]+edge[i])/oud[x]$ #### 正推：$dp[i]$表示从$1$到$i$的期望，$g[i]$表示从$1$到$i$的概率，方程的转移：对于一条从$x$到$y$的边 #### $dp[y]=\sum\limits_{i=1}^{ind[y]}(dp[x]+edge[i]\times g[x])/oud[x]$ #### why? #### 逆推： #### $E(y)=p_1x_1+p_2x_2+\cdots\cdots+p_nx_n$ #### $E(x)=p_1(x_1+w)+p_2(x_2+w)+\cdots\cdots+p_n(x_n+w)=E(y)+\sum\limits_{i=1}^np_i\times w=E(y)+w$ ### 因为从$i$到$n$,所有概率和为$1$ #### 正推： #### $E(x)=p_1x_1+p_2x_2+\cdots\cdots+p_nx_n$ #### $E(y)=p_1(x_1+w)+p_2(x_2+w)+\cdots\cdots+p_n(x_n+w)=E(x)+\sum\limits_{i=1}^np_i\times w\neq E(x)+w$ ### 因为从$1$到$i$，所有概率和i不为1 #### CODE（正推）: ``` #include<cstdio> #include<cstring> #include<iostream> #include<queue> using namespace std; const int MAXX=100010; int oud[MAXX],ind[MAXX],ver[MAXX<<1],nxt[MAXX<<1],head[MAXX],edge[MAXX<<1]; double dp[MAXX],g[MAXX]; int tot,n,m; inline void add(int x,int y,int z){ ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edge[tot]=z; oud[x]++; ind[y]++; } inline void topsort(){ queue<int>q; for(int i=1;i<=n;++i)if(!ind[i])q.push(i); dp[1]=0.000; g[1]=1.000; while(q.size()){ int x=q.front(); q.pop(); for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; dp[y]+=(dp[x]*g[x]+(double)edge[i]*g[x])/(double)oud[x]; g[y]+=g[x]/(double)oud[x]; if(--ind[y]==0)q.push(y); } } } int main(){ cin>>n>>m; for(int i=1;i<=m;++i){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } topsort(); printf("%.2lf",dp[n]); return 0; } ``` #### CODE2（逆推 )为了方便更新我们建了反图，但是出度以原图为准 ``` #include<cstdio> #include<cstring> #include<iostream> #include<queue> using namespace std; const int MAXX=100010; int head[MAXX],ver[MAXX<<1],nxt[MAXX<<1],edge[MAXX<<1],ind[MAXX],oud[MAXX]; int tot,n,m; double dp[MAXX]; inline void add(int x,int y,int z){ ver[++tot]=y; nxt[tot]=head[x]; head[x]=tot; edge[tot]=z; } inline void topsort(){ queue<int>q; dp[n]=0; for(int i=1;i<=n;++i)if(!ind[i])q.push(i); while(q.size()){ int x=q.front(); q.pop(); for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; dp[y]+=(dp[x]+(double)edge[i])/(double)oud[y]; if(--ind[y]==0)q.push(y); } } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;++i){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(y,x,z); ind[x]++; oud[x]++; } topsort(); printf("%0.2lf",dp[1]); return 0; } ```