首页 > 代码库 > [hdu4035] Maze【概率dp 数学期望】
[hdu4035] Maze【概率dp 数学期望】
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4035
真的是一道好题,题解比较麻烦,我自己在纸上写了好大一块草稿才搞出来,不用公式编辑器的话就很难看清楚,所以不上题解啦,贴一个题解的链接:http://blog.csdn.net/balloons2012/article/details/7891054
注意此题卡精度,我一开始eps是1e-8,WA掉了,开到了1e-10,AC~,真是烦卡精度的题。
#include <cstdio> #include <cstring> #include <cmath> const int maxn = 20005; int T, n, t1, t2, k[maxn], e[maxn]; int head[maxn], to[maxn << 1], next[maxn << 1], lb, out[maxn]; double a[maxn], b[maxn], c[maxn]; inline void ist(int aa, int ss) { to[lb] = ss; next[lb] = head[aa]; head[aa] = lb; ++lb; ++out[aa]; } bool dfs(int r, int p) { if (r > 1 && out[r] == 1) { a[r] = (double)k[r] / 100.0; b[r] = c[r] = (double)(100 - k[r] - e[r]) / 100.0; return true; } for (int j = head[r]; j != -1; j = next[j]) { if (to[j] != p) { dfs(to[j], r); a[r] += a[to[j]]; b[r] += b[to[j]]; c[r] += c[to[j]]; } } double tem = 1.0 - (100 - k[r] - e[r]) * b[r] / 100.0 / out[r]; if (fabs(tem) < 1e-10) { return false; } a[r] = ((k[r] / 100.0) + (100 - k[r] - e[r]) * a[r] / 100.0 / out[r]) / tem; b[r] = (100 - k[r] - e[r]) / 100.0 / out[r] / tem; c[r] = ((100 - k[r] - e[r]) / 100.0 + (100 - k[r] - e[r]) * c[r] / 100.0 / out[r]) / tem; return true; } int main(void) { //freopen("in.txt", "r", stdin); scanf("%d", &T); for (int kase = 1; kase <= T; ++kase) { printf("Case %d: ", kase); memset(head, -1, sizeof head); memset(next, -1, sizeof next); lb = 0; memset(out, 0, sizeof out); memset(a, 0, sizeof a); memset(b, 0, sizeof b); memset(c, 0, sizeof c); scanf("%d", &n); for (int i = 1; i < n; ++i) { scanf("%d%d", &t1, &t2); ist(t1, t2); ist(t2, t1); } for (int i = 1; i <= n; ++i) { scanf("%d%d", k + i, e + i); } if (dfs(1, 0) && fabs(1.0 - a[1]) > 1e-10) { printf("%f\n", c[1] / (1.0 - a[1])); } else { puts("impossible"); } } return 0; }
[hdu4035] Maze【概率dp 数学期望】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。