首页 > 代码库 > Hdu 2376
Hdu 2376
题目链接
题意:给出一颗含有n个结点的树,树上每条边都有一个长度,求树上所有路径的平均长度。
考虑树上每条边对所有路径长度和的贡献,对于每条偶 就是边的两个短点u和v,只需要记录以u为根的子树的结点的个数,
那么不在结点u为根的子树上的结点个数为n-count[u], 所有该边对总长度的贡献就是count[u] * (n - count[u]) * cost.
最后用总长度除以总的边数(n * (n - 1) / 2)., 有点坑的是:eps我调到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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。