hdu 5425 Rikka with Tree II(暴力)

作者:郫县华伟包装厂 来源:www.cdhwms.com 发布时间:2017-09-11 14:02:21
hdu 5425 Rikka with Tree II(暴力)

直接枚举就好了,当概率极小时贡献值可以忽略。

#include #include #include #include #include #include using namespace std; const int maxn = 1e5 + 5; int N, D[maxn]; vector G[maxn]; void init () { for (int i = 1; i <= N; i++) G[i].clear(); int t; for (int i = 2; i <= N; i++) { scanf(%d, &t); G[t].push_back(i); } queue Q; D[1] = 0; Q.push(1); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; D[v] = D[u] + 1; Q.push(v); } } sort(D + 1, D + 1 + N); } int main () { while (scanf(%d, &N) == 1) { init (); double ans = 0; for (int i = 0; i < N && i < 100; i++) { int u = N - i; double w = 0; for (int j = N; j > u; j--) w += 1.0 * (D[u] + 1) * (D[j] + 1) / (D[u] + D[j] + 2); double t = pow(2, N-u+1) - (N+1) / pow(2, u-1); ans += w / t; } printf(%.6lf , ans); } return 0; }

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:荆门SEO http://jingmen.raoyu.net

  • 上一篇:.Net Web项目安装包制作(三)补充说明
  • 下一篇:最后一页