hdu 2736 Average distance

传送门

Average distance

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 682    Accepted Submission(s): 244
Special Judge

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

Source

bapc2007

Recommend

lcy   |   We have carefully selected several similar problems for you:  2378 2379 2377 2380 2381

哎,思路想复杂了,其实蛮简单的:

转一发题解:

引:如果暴力枚举两点再求距离是显然会超时的。转换一下思路,我们可以对每条边,求所有可能的路径经过此边的次数:设这条边两端的点数分别为A和B,那 么这条边被经过的次数就是A*B,它对总的距离和的贡献就是(A*B*此边长度)。我们把所有边的贡献求总和,再除以总路径数N*(N-1)/2,即为最 后所求。

每条边两端的点数的计算,实际上是可以用一次dfs解决的。任取一点为根,在dfs的过程中,对每个点k记录其子树包含的点数(包括其自身),设点数为a[k],则k的父亲一侧的点数即为N-a[k]。这个统计可以和遍历同时进行。故时间复杂度为O(n)。

16447376 2016-03-06 09:40:59 Accepted 2376 312MS 4540K 2093 B C++ czy
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stack>
 6 #include <cctype>
 7 #include <vector>
 8 #include <cmath>
 9 #include <map>
10 #include <queue>
11
12 #define ll long long
13 #define N 10005
14 #define eps 1e-8
15
16 using namespace std;
17
18 int T;
19 double tot[N];
20 double cou[N];
21 double num;
22 int n;
23
24 struct PP
25 {
26     int to;
27     double val;
28 };
29
30 vector<PP>Edge[N];
31
32 PP te;
33
34 void add_adge(int from,int to,double val)
35 {
36     te.to = to;te.val = val;
37     Edge[from].push_back(te);
38     te.to = from;te.val = val;
39     Edge[to].push_back(te);
40 }
41
42 void dfs(int now,int fa)
43 {
44     unsigned int i;
45     PP nt;
46     cou[now] = 1;
47     for(i = 0;i < Edge[now].size();i++){
48         nt.to = Edge[now][i].to;
49         nt.val = Edge[now][i].val;
50         if(nt.to == fa){
51             continue;
52         }
53         dfs(nt.to,now);
54         tot[now] = tot[now] + tot[nt.to] + (n-cou[nt.to]) * cou[nt.to] * nt.val;
55         cou[now] = cou[now] + cou[nt.to];
56         //printf("  now = %d i=%d to=%d tot=%.6f cou=%.6lf\n",now,i,nt.to,tot[now],cou[now]);
57     }
58     //printf(" i=%d tot=%.6f cou=%.6f\n",now,tot[now],cou[now]);
59 }
60
61 int main()
62 {
63     //freopen("in.txt","r",stdin);
64     scanf("%d",&T);
65     int i;
66     int from,to;
67     double val;
68     for(int ccnt=1;ccnt<=T;ccnt++){
69     //while(scanf("%lf%lf%lf%lf",&a[0],&a[1],&a[2],&a[3])!=EOF){
70         scanf("%d",&n);
71         memset(tot,0,sizeof(tot));
72         memset(cou,0,sizeof(cou));
73         num = 1.0 *n*(n-1)/2;
74         for(i=0;i<=n;i++){
75             Edge[i].clear();
76         }
77         for(i=1;i<=n-1;i++){
78             scanf("%d%d%lf",&from,&to,&val);
79             add_adge(from,to,val);
80         }
81         dfs(0,-1);
82         //for(i=0;i<n;i++){
83          //   for(int j=0;j<Edge[i].size();j++){
84          //       printf(" i=%d to=%d val=%.6lf\n",i,Edge[i][j].to,Edge[i][j].val);
85          //   }
86        // }
87         for(i=0;i<n;i++){
88             //printf(" i=%d tot=%.6f cou=%.6f\n",i,tot[i],cou[i]);
89         }
90         printf("%lf\n",tot[0]/num);
91     }
92     return 0;
93 }
时间: 03-06

hdu 2736 Average distance的相关文章

HDU 4712 Hamming Distance (随机函数)

Hamming Distance Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1806    Accepted Submission(s): 714 Problem Description (From wikipedia) For binary strings a and b the Hamming distance is equal

hdu 5903 Square Distance(dp)

Problem Description A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not. Hamming distanc

hdu 4712 Hamming Distance(随机数法)

d.汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量, 我们以d(x,y)表示两个字x,y之间的汉明距离.对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离. 给出N个串,求出其中最小的汉明距离(其中某2个串的汉明距离是最小的). s.随机数法... c.能不能过,看脸... #include<iostream> #include<stdio.h> #include<string.h> #inc

HDU 5353 Average

题意:有n个人坐在圆桌上,每个人带着糖果若干,每次只能给旁边的人1科糖果,而且坐相邻的两个人最多只能给一次(要么你给我,要么我给你),问是否能将糖果平均分了. 思路:明显每个人最多只能多于平均值2个糖果,因为他只能分别往左和右边的人给1颗.而多于平均值1的人可以任意选1个方向,只要到最后所有人满足了即可.多余糖果超过3的.平均数是浮点型的都是无解. 在第i和第i+1个人之间建两条边(即无向边拆成2条有向边),分别从一方指向另一方.1和n也建两条.分两步: (1)将持有2个多余糖果的人先处理,用D

HDU 5903 Square Distance

$dp$预处理,贪心. 因为$t$串前半部分和后半部分是一样的,所以只要构造前一半就可以了. 因为要求字典序最小,所以肯定是从第一位开始贪心选择,$a,b,c,d,...z$,一个一个尝试过去,如果发现某字符可行,那么该位就选择该字符. 第$i$位选择字符$X$可行的条件: 记这一位选择字符$X$的情况下,对$dis$的贡献为$Q$,$1$至$i-1$位对$dis$贡献和为$F$: 如果第$i+1$位至第$\frac{n}{2}$位,对$dis$的贡献可以凑出$m-Q-F$,那么该位选择$X$可

Soj题目分类

-----------------------------最优化问题------------------------------------- ----------------------常规动态规划  SOJ1162 I-Keyboard  SOJ1685 Chopsticks SOJ1679 Gangsters SOJ2096 Maximum Submatrix  SOJ2111 littleken bg SOJ2142 Cow Exhibition  SOJ2505 The County

PAT 1004 To Fill or Not to Fill (25)

题目描写叙述 With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are

Cracking The Vigenere Cipher

In order to crack "Vigenere Cipher" under the circumstance that the key length can be only 3, 4 or 5, I used frequency analysis to find possible keys and compared the Euclidean distance of all candidate keys calculated with "Relative freque

Isolation-based Anomaly Detection

Anomalies are data points that are few and different. As a result of these properties, we show that, anomalies are susceptible to a mechanism called isolation. This paper proposes a method called Isolation Forest (iForest) which detects anomalies pur