[HDU4035] Maze（概率DP）

HDU4035

有\(n\)个房间 , 由\(n-1\)条隧道连通起来 , 实际上就形成了一棵树 , 从结点\(1\)出发 , 开始走 , 在每个结点\(i\)都有\(3\)种可能 :

\(1.\)被杀死 , 回到结点\(1\)处 (概率为\(k_i\))

\(2.\)找到出口 , 走出迷宫 (概率为\(e_i\))

\(3.\)和该点相连有\(m\)条边 , 随机走一条

求走出迷宫所要走的边数的期望值

题解

\(1.\)设对每个结点转化为：\(E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;\) $ \ \ $方便dfs中转移

\(2.\)推式子要考虑清楚叶节点的情况 , 要记得乘上概率\(\frac{1}{m}\)

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<vector>

#include<cmath>

#define debug(...) fprintf(stderr,__VA_ARGS__)

#define Debug(x) cout<<#x<<"="<<x<<endl

using namespace std;

typedef long long LL;

const int INF=1e9+7;

inline LL read(){

	register LL x=0,f=1;register char c=getchar();

	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}

	while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();

	return f*x;

}

const int MAXN=1e4+5;

const double eps=1e-9;

double A[MAXN],B[MAXN],C[MAXN],e[MAXN],k[MAXN];

int n,T;

vector <int> G[MAXN];

inline bool dfs(int u,int pre){

	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 tmp=0;

	for(int i=0;i<m;i++){

		int v=G[u][i];

		if(v==pre) 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];

		tmp+=(1-k[u]-e[u])/m*B[v];

	}

	if(fabs(tmp-1)<eps) return false;//如果$Ei$的系数趋向于0则无解

	A[u]/=(1-tmp);//很巧妙地对于叶子节点答案也是正确的

	B[u]/=(1-tmp);

	C[u]/=(1-tmp);

	return true;

}

int main(){

	T=read();

	for(int Case=1;Case<=T;Case++){

		n=read();

		for(int i=1;i<=n;i++) G[i].clear();

		for(int i=1;i<=n-1;i++){

			int x=read(),y=read();

			G[x].push_back(y);

			G[y].push_back(x);

		}

		for(int i=1;i<=n;i++){

			k[i]=(double)read()/100.0;

			e[i]=(double)read()/100.0;

		}

		if((!dfs(1,0))||(fabs(1-A[1])<eps)) printf("Case %d: impossible\n",Case);

		else printf("Case %d: %.6lf\n",Case,C[1]/(1-A[1]));

	}

}