首页 > 代码库 > Hdu 2376

Hdu 2376

2024-07-27 19:11:40   217人阅读

题目链接

题意：给出一颗含有ｎ个结点的树，树上每条边都有一个长度，求树上所有路径的平均长度。

考虑树上每条边对所有路径长度和的贡献，对于每条偶　就是边的两个短点ｕ和ｖ，只需要记录以u为根的子树的结点的个数，

那么不在结点ｕ为根的子树上的结点个数为ｎ－count[u], 所有该边对总长度的贡献就是count[u] * (n - count[u]) * cost.

最后用总长度除以总的边数(n * (n - 1) / 2).，　有点坑的是：ｅｐｓ我调到1e-11才过。。。

 1 /************************************************************************* 2     > File Name: 2376.cpp 3     > Author: Stomach_ache 4     > Mail: sudaweitong@gmail.com 5     > Created Time: 2014年10月17日 星期五 23时10分56秒 6     > Propose:  7  ************************************************************************/ 8 #include <cmath> 9 #include <string>10 #include <cstdio>11 #include <vector>12 #include <fstream>13 #include <iomanip>14 #include <cstring>15 #include <iostream>16 #include <algorithm>17 using namespace std;18 /*Let‘s fight!!!*/19 20 typedef pair<int, int> pii;21 typedef long long LL;22 vector<pii> G[10050];23 LL res;24 //int tot[10050];25 int n;26 27 int dfs(int u, int fa) {28       int sz = G[u].size();29     //tot[u] = 1;30 //    if (sz == 1) return 1;31     int tot = 1;32     for (int i = 0; i < sz; i++) {33           int v = G[u][i].first, w = G[u][i].second;34           if (v != fa) {35               int cnt = dfs(v, u);36             tot += cnt;37             res += (LL)cnt * (n - cnt) * w;38         }39     }40     return tot;41 }42 43 int main(void) {44       ios::sync_with_stdio(false);45       int t;46     cin >> t;47     while (t--) {48         cin >> n;49         for (int i = 0; i < n; i++) G[i].clear();50         for (int i = 1; i < n; i++) {51               int u, v, w;52             cin >> u >> v >> w;53             G[u].push_back(pii(v, w));54             G[v].push_back(pii(u, w));55         }56         res = 0;57         dfs(0, -1);58         cout << fixed << setprecision(11) << (res + 0.0) / (n * (n - 1) / 2) << endl;59     }60     return 0;61 }

 

Hdu 2376


联系
我们