首页 > ACM题库 > HDU-杭电 > hdu 2376 Average distance-动态规划-[解题报告]C++
2014
01-05

hdu 2376 Average distance-动态规划-[解题报告]C++

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

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2376

思路:

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

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

#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;
 }

 

 

解题转自:http://www.cnblogs.com/wally/archive/2013/06/03/3116020.html


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

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

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?