HDU 4035 Maze （树状dp + 概率）

本文主要是介绍HDU 4035 Maze （树状dp + 概率），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OJ题目 ： click here ~~~

题目分析 :这篇文章已经说的很好很好了 ， 直接借用 ，猛戳~~

int n;
double k[10002] , e[10002];
double A[10002] , B[10002] , C[10002];
vector<int> List[10002];bool dfs(int u , int father)
{if(List[u].size() == 1&&father != -1){A[u] = k[u];B[u] = 1 - k[u] - e[u];C[u] = 1 - k[u] - e[u];return true;}A[u] = k[u];B[u] = (1 - k[u] - e[u])/List[u].size();C[u] = 1 - k[u] - e[u];double temp = 0;for(int i = 0;i < List[u].size();i++){int v = List[u][i];if(v == father) continue;if(!dfs(v , u)) return false;A[u] += A[v]*B[u];C[u] += C[v]*B[u];temp += B[u]*B[v];}if(fabs(temp - 1) < 1e-10) return false;A[u] /= (1 - temp);B[u] /= (1 - temp);C[u] /= (1 - temp);return true;}
int main()
{int Case;cin >> Case;for(int cas = 1;cas <= Case;cas++){cin >> n;int i , j , a, b;for(i = 0;i <= n;i++) List[i].clear();for(i = 1;i < n;i++){scanf("%d%d",&a,&b);List[a].push_back(b);List[b].push_back(a);}for(i = 1;i <= n;i++){scanf("%lf%lf",&k[i],&e[i]);k[i] /= 100;e[i] /= 100;}dfs(1 , -1);printf("Case %d: ",cas);if(fabs(1 - A[1]) < 1e-10)printf("impossible\n");elseprintf("%lf\n",C[1]/(1-A[1]));}return 0;
}

这篇关于HDU 4035 Maze （树状dp + 概率）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---