acgo题库
  • 首页
  • 题库
  • 学习
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情提交记录(0)
  • 题解

    #include <cstdio> #include <vector> #include <cmath> using namespace std; const int N = 5e5 + 10; const double EPS = 1e-8; vector<pair<int, double>> G[N]; double q[N], f[N], g[N], ans; void dfs1(int u, int fa) { f[u] = 1.0 - q[u]; for (auto &e : G[u]) { int v = e.first; double p = e.second; if (v == fa) continue; dfs1(v, u); f[u] *= (1.0 - p + p * f[v]); } } void dfs2(int u, int fa) { ans += 1.0 - g[u]; for (auto &e : G[u]) { int v = e.first; double p = e.second; if (v == fa) continue; double deno = 1.0 - p + p * f[v]; if (fabs(deno) < EPS) { g[v] = f[v] * (1.0 - p); } else { double T = g[u] / deno; g[v] = f[v] * (1.0 - p + p * T); } dfs2(v, u); } } int main() { int n; scanf("%d", &n); for (int i = 1; i < n; ++i) { int a, b, p_val; scanf("%d%d%d", &a, &b, &p_val); double prob = p_val / 100.0; G[a].emplace_back(b, prob); G[b].emplace_back(a, prob); } for (int i = 1; i <= n; ++i) { int q_val; scanf("%d", &q_val); q[i] = q_val / 100.0; } dfs1(1, -1); g[1] = f[1]; dfs2(1, -1); printf("%.6lf\n", ans); return 0; }

    userId_undefined

    我不是AC君

    时间刺客空间掌握者时空双修者贪心·贪心尝试者倔强青铜递归·套娃学徒
    3阅读
    0回复
    1点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页