題目鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=4035

題目意思：

有n個房間，有n-1條通道連接這n個房間（每兩個房間之間有且只有一條路，所以實際上就是一棵樹），在每個房間中，有三種選擇要么被殺則回到第一個房間，概率為ki,要么從出口逃離概率為ei,要么通過通道到達其他的房間。

解題思路：

好題。

狀態轉移方程很好想，但是求的時候有技巧，不能直接用高斯消元來求（n有10000）肯定會超時。發現知，此題是在一棵樹上轉移，所以可以借助樹的特點，分成兩部分兒子和父親，抽象出系數，然后從葉子節點向上求出父親節點。

以下文字選自http://blog.csdn.net/morgan_xww/article/details/6776947

設 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<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<ctime> #define eps 1e-9 #define INF 0x3fffffff #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;#define Maxn 10100int deg[Maxn],cnt,n; double A[Maxn],B[Maxn],C[Maxn]; //分別表示系數 double k[Maxn],e[Maxn];//表示被殺和逃離概率struct Edge {int v;struct Edge * next; }edge[Maxn<<1],*head[Maxn<<1];void add(int a,int b) {++cnt;deg[a]++; //度數edge[cnt].v=b,edge[cnt].next=head[a];head[a]=&edge[cnt]; } void dfs(int cur,int pre) {struct Edge * p=head[cur];bool flag=true;double suma=0,sumb=0,sumc=0;while(p){int v=p->v;if(v!=pre){flag=false; //不是葉子節點dfs(v,cur);suma+=A[v];sumb+=B[v];sumc+=C[v];} //求出兒子節點的各和p=p->next;}if(flag) //葉子節點{double t=1-k[cur]-e[cur];A[cur]=k[cur],B[cur]=t,C[cur]=t;return ;}//非葉子節點double temp=(1-k[cur]-e[cur])/deg[cur];double tt=1-temp*sumb;A[cur]=(k[cur]+temp*suma)/tt;B[cur]=temp/tt;C[cur]=(temp*sumc+(1-k[cur]-e[cur]))/tt;return ; }int main() {int t;scanf("%d",&t);for(int ca=1;ca<=t;ca++){scanf("%d",&n);memset(head,NULL,sizeof(head));memset(deg,0,sizeof(deg));cnt=0;for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}for(int i=1;i<=n;i++){double a,b;scanf("%lf%lf",&a,&b);k[i]=a/100.0,e[i]=b/100.0;}dfs(1,-1);printf("Case %d: ",ca);if(fabs(1-A[1])<eps) //這里卡精度printf("impossible\n");elseprintf("%.5f\n",C[1]/(1.0-A[1]));}return 0; }

?

?

總結

以上是生活随笔為你收集整理的借助树的概率dp(期望)+数学-好题-hdu-4035-Maze的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。