shunfurh 于 2016.12.31 19:19 提问

Average distance

Problem Description
Given a tree, calculate the average distance between two vertices in the tree. For example, the average distance between two vertices in the following tree is (d01 + d02 + d03 + d04 + d12 +d13 +d14 +d23 +d24 +d34)/10 = (6+3+7+9+9+13+15+10+12+2)/10 = 8.6.

Input
On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (2 <= n <= 10 000): the number of nodes in the tree. The nodes are numbered from 0 to n - 1.

n - 1 lines, each with three integers a (0 <= a < n), b (0 <= b < n) and d (1 <= d <= 1 000). There is an edge between the nodes with numbers a and b of length d. The resulting graph will be a tree.

Output
For each testcase:

One line with the average distance between two vertices. This value should have either an absolute or a relative error of at most 10-6

Sample Input
1
5
0 1 6
0 2 3
0 3 7
3 4 2

Sample Output
8.6

2个回答

caozhy      2016.12.31 19:16

sinat_37181010   2016.12.31 21:42

Fast marching on 3D meshes with diffusion distance

hdu2376 Average distance

average diffusion distance
average diffusion distance implemented in matlab

Learning_PN_Toolbox

Hausdorff distance的模板匹配
﻿﻿ 一、  Hausdorff距离匹配算法及代码 http://blog.csdn.net/holamirai/article/details/48351019 二、http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html#whatis 三、OpenCV 谈openc
LeetCode 346. Moving Average from Data Stream（数据流移动平均值）

【hdu 2376】Average distance
【题目链接】:http://acm.hdu.edu.cn/showproblem.php?pid=2376【题意】 让你计算树上任意两点之间的距离的和. 【题解】 算出每条边的两端有多少个节点设为num1和num2; 这条边的边权为w; 答案累加上w*num1*num2; 然后总的答案除n*(n-1)/2; 【完整代码】#include <bits/stdc++.h> us