2014
01-05

# Average distance

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.

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.

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.

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

8.6

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define MAXN 10000+10
struct Node{
int v,len;
};
vector<Node>vet[MAXN];
int n;
double dp[MAXN];
int sum[MAXN];

void dfs(int root,int father){
sum[root]=1;
for(int i=0;i<vet[root].size();i++){
int son=vet[root][i].v;
int len=vet[root][i].len;
if(son==father)continue;
dfs(son,root);
sum[root]+=sum[son];
dp[root]+=dp[son]+(sum[son]*(n-sum[son]))*(double)len;
}
}

int main(){
//  freopen("1.txt","r",stdin);
int _case,u,v,len;
scanf("%d",&_case);
while(_case--){
scanf("%d",&n);
for(int i=0;i<=n;i++)vet[i].clear();
for(int i=1;i<=n-1;i++){
scanf("%d%d%d",&u,&v,&len);
Node p1,p2;
p1.v=v,p2.v=u;
p1.len=p2.len=len;
vet[u].push_back(p1);
vet[v].push_back(p2);
}
memset(sum,0,sizeof(sum));
memset(dp,0,sizeof(dp));
dfs(0,-1);
int s=(n*(n-1)/2);
printf("%1lf\n",(double)dp[0]/s);
}
return 0;
}

1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。

3. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;