[HDU4035]Maze（概率与期望）

=== ===

这里放传送门

=== ===

题解

可以想到用 f[i] 表示从点i逃出去的期望步数。但是这个题因为它有一个概率回到1号点重新开始，所以会存在互相推的问题。通用的解决办法是高斯消元，但这个题的数据范围显然没有办法消。。。

但是题目给的是一棵树，能不能利用这个特点？ 设 P[i] 为从点i逃到其它点的概率，就是 P[i]=1−k[i]−e[i]d[i] 。首先列出递推式：

f[i]=∑son(f[son]+1)∗P[i]+(f[fa]+1)∗P[i]+f[1]∗k[i] 如果利用类似树形DP的方法用儿子的结果更新父亲的话， f[fa] 和 f[1] 就都是未知数，而 f[son] 是已知数，在递推 f[i] 的时候可以当做一个常量。 那么设 f[i]=A[i]∗f[fa]+B[i]∗f[1]+C[i] 。我们希望得到关于 A[i]，B[i] 和 C[i] 的递推式。为了递推就需要在式子里面引入 A[son]，B[son] 和 C[son] 。利用 f[son]=A[son]∗f[i]+B[son]∗f[1]+C[son] 来代入上面的递推式，得到： f[i]=∑son(A[son]∗f[i]+B[son]∗f[1]+C[son]+1)∗P[i]+(f[fa]+1)∗P[i]+f[1]∗k[i] 把这个式子展开，把同类项合并，得到 (1−∑sonA[son]∗P[i])∗f[i]=f[fa]∗P[i]+(∑sonB[son]∗P[i]+k[i])∗f[1]+∑son(C[son]+1)∗P[i]+P[i] 那么如果设 T[i]=1−∑sonA[son]∗P[i] ，就有 A[i]=P[i]T[i] ， B[i]=∑sonB[son]∗P[i]+k[i]T[i] ， C[i]=(∑sonC[son]∗P[i])+d[i]∗P[i]T[i] 。一遍树形DP就可以求出 A[1] ， B[1] 和 C[1] 。而因为节点1没有父亲，所以 f[1]=B[1]∗f[1]+C[1] ，也就是 f[1]=C[1]1−B[1] 。计算过程中只要出现被零除的情况就说明无解，输出impossible即可。

代码

#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const double eps=1e-10; int T,n,p[10010],a[20010],tot,nxt[20010]; double A[10010],B[10010],C[10010],P[10010],d[10010],K[10010],E[10010]; bool flag; void add(int x,int y){ tot++;a[tot]=y;nxt[tot]=p[x];p[x]=tot; } void dfs(int u,int fa){ double tmp=0; A[u]=P[u];B[u]=K[u]; C[u]=1-K[u]-E[u]; for (int i=p[u];i!=0;i=nxt[i]) if (a[i]!=fa){ dfs(a[i],u); if (flag==true) return; tmp+=A[a[i]]*P[u]; B[u]+=B[a[i]]*P[u]; C[u]+=C[a[i]]*P[u]; } tmp=1.0-tmp; if (fabs(tmp)<eps){flag=true;return;} A[u]/=tmp;B[u]/=tmp;C[u]/=tmp; } int main() { scanf("%d",&T); for (int wer=1;wer<=T;wer++){ scanf("%d",&n);tot=0; memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); for (int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); add(x,y);add(y,x); d[x]+=1;d[y]+=1; } for (int i=1;i<=n;i++){ scanf("%lf%lf",&K[i],&E[i]); K[i]/=100.0;E[i]/=100.0; } for (int i=1;i<=n;i++) P[i]=(1-K[i]-E[i])/d[i]; flag=false;dfs(1,0); printf("Case %d: ",wer); if (flag==true||fabs(1.0-B[1])<eps) printf("impossible\n"); else printf("%.6lf\n",C[1]/(1-B[1])); } return 0; }

偏偏在最后出现的补充说明

这类题目是概率与期望题目中经常出现的一个类型。在没有办法使用高斯消元的时候要注意观察题目的性质，有些时候会给出具有明显递推特性的结构。基本思路就是设未知量然后由直接递推答案转为递推未知量的系数。