首页 > 代码库 > hdu4035（概率dp）
hdu4035（概率dp）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4035
题意：有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树， 从结点1出发，开始走，在每个结点i都有3种可能：
1.被杀死，回到结点1处（概率为ki）
2.找到出口，走出迷宫 （概率为ei）
3.和该点相连有m条边，随机走一条
求：走出迷宫所要走的边数的期望值。
分析：这题得有很强的递推能力才递推得出来吧，下面是网上的解释：
设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。E[1]即为所求。 叶子结点： E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1); = ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei); 非叶子结点：（m为与结点相连的边数） E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) ); = ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei); 设对每个结点：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci; 对于非叶子结点i，设j为i的孩子结点，则 ∑(E[child[i]]) = ∑E[j] = ∑(Aj*E[1] + Bj*E[father[j]] + Cj) = ∑(Aj*E[1] + Bj*E[i] + Cj) 带入上面的式子得 (1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + (1-ki-ei)/m*∑Cj; 由此可得 Ai = (ki+(1-ki-ei)/m*∑Aj) / (1 - (1-ki-ei)/m*∑Bj); Bi = (1-ki-ei)/m / (1 - (1-ki-ei)/m*∑Bj); Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj ) / (1 - (1-ki-ei)/m*∑Bj); 对于叶子结点 Ai = ki; Bi = 1 - ki - ei; Ci = 1 - ki - ei; 从叶子结点开始，直到算出 A1,B1,C1; E[1] = A1*E[1] + B1*0 + C1; 所以 E[1] = C1 / (1 - A1); 若 A1趋近于1则无解...
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;double A[N],B[N],C[N];double k[N],e[N];vector<int>g[N];bool dfs(int u,int fa){ int m=g[u].size(); A[u]=k[u]; B[u]=(1-k[u]-e[u])/m; C[u]=1-k[u]-e[u]; double temp=0; for(int i=0;i<m;i++) { int v=g[u][i]; if(v==fa)continue; if(!dfs(v,u))return false; A[u]+=(1-k[u]-e[u])/m*A[v]; C[u]+=(1-k[u]-e[u])/m*C[v]; temp+=(1-k[u]-e[u])/m*B[v]; } if(fabs(1-temp)<eps)return false; A[u]/=(1-temp); B[u]/=(1-temp); C[u]/=(1-temp); return true;}int main(){ int T,n,u,v,cas=1; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<n;i++) { scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } for(int i=1;i<=n;i++) { scanf("%lf%lf",&k[i],&e[i]); e[i]/=100;k[i]/=100; } printf("Case %d: ",cas++); if(dfs(1,-1)&&fabs(A[1]-1)>eps) { printf("%.6lf\n",C[1]/(1-A[1])); } else puts("impossible"); }}
hdu4035（概率dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。