首页 > ACM题库 > HDU-杭电 > Hdu 1706 The diameter of graph 待解决 [解题报告] C++
2013
12-21

Hdu 1706 The diameter of graph 待解决 [解题报告] C++

The diameter of graph

问题描述 :

The graph diameter is the length of the "longest shortest path" between any two vertices of a graph. In other words, a graph’s diameter is the longest path which must be traversed in order to travel from any vertex to another when paths which backtrack, detour, or loop are excluded from consideration.
Given an undirected graph, your mission is to count the number of diameters of it.

输入:

The input contains multiple test cases.
For each test case, it contains n+1 lines.
Line 1: two integers m, n (2<= m <= 100, 1 <= n <= 4000) indicating that there are m vertices and n edges in the city.
Line 2~n+1: each contains three integers i, j, d (1 <= i, j <= m, 1 <= d <= 100), indicating that there is an edge of length d connecting vertex i and vertex j.

输出:

Output the value of the diameter and the number of diameters in a single line, separated by a single space.

样例输入:

4 5 
1 2 1 
2 3 1 
3 4 1 
1 4 1 
1 3 2 

样例输出:

2 5


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  3. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.