求大神指教！c/c++上机题目
本帖最后由 woohyukwon 于 2013-11-24 18:07:46 编辑 Description
After the war between Country X and Country Y, all the roads in Country X have been destroyed. Qiqi, the king of Country X wants to build some roads to connect all cities (it means that starting from every city, we can go to any other cities through roads Qiqi built) as soon as possible.
Every road takes one day to build and every day Qiqi can build only one road. Building the road between city i and city j costs |pi - pj| units money, where pi and pj are the population of city i and city j. What is the maximum and minimum cost if Qiqi wants to connect all cities in the shortest time?
Input
There are multiple test cases. The first line of the input will be an integer T (T <= 50) indicating the number of test cases.
For each test case there is an integer N (1 <= N <= 1000) in a single line, representing the number of cities in Country X. The next line lists N integers describing the population of each city.
All cities' population are between 1 and 10000(inclusive).
OutputFor each test case, print "Case #t: " first, in which t is the number of the test case starting from 1. Then output the minimum and maximum cost.
Sample Input1
3
1 2 3
Sample Output
Case #1: 2 3
Hint
Huge input/output. Please use scanf/printf for C/C++.
For the first sample, we can build the roads between 1 and 2, 2 and 3 to get the minimum cost of 2. And build the roads between 1 and 2, 1 and 3 to get the maximum cost of 3.
求详细解答过程步骤 c语言 c++ 编程 上机
[解决办法]
目测是个最小生成树问题，N = 1000的数量级，直接Prim算法就行了，复杂度O(N*N)
[解决办法]
CSDN的论坛里都有的，你搜一下就知道了，这里随便提供一篇：http://blog.csdn.net/i_want_to_be_a_god/article/details/16911041
[解决办法]
以下任选
Prim算法，每次添加权重最高的边
Kruskal算法，每次删除权重最小的边
[解决办法]
《算法精解（C语言实现）》里面有完整的代码。
