线性表的聚合操作的问题的一个实现的算法,采用C语言的办法如何解决

Problem Description
An abandoned country has n(n≤100000) villages which are numbered from 1 to n. Since abandoned for a long time, the roads need to be re-built. There are m(m≤1000000) roads to be re-built, the length of each road is wi(wi≤1000000). Guaranteed that any two wi are different. The roads made all the villages connected directly or indirectly before destroyed. Every road will cost the same value of its length to rebuild. The king wants to use the minimum cost to make all the villages connected with each other directly or indirectly. After the roads are re-built, the king asks a men as messenger. The king will select any two different points as starting point or the destination with the same probability. Now the king asks you to tell him the minimum cost and the minimum expectations length the messenger will walk.

Input
The first line contains an integer T(T≤10) which indicates the number of test cases.

For each test case, the first line contains two integers n,m indicate the number of villages and the number of roads to be re-built. Next m lines, each line have three number i,j,wi, the length of a road connecting the village i and the village j is wi.

Output
output the minimum cost and minimum Expectations with two decimal places. They separated by a space.

Sample Input
1
4 6
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5
2 4 6

Sample Output
6 3.33

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

4
CRC校验代码看不懂,请求高手支招。目前我看不懂的一篇CRC校验文章和一套逆序CRC校验。
2
02-线性结构2 一元多项式的乘法与加法运算,这道题的代码上的问题
2
C语言中代码执行顺序错误
1
将所有的在线性表Lb中但不在La中的元素插入La中
2
链表线性表的增和删,希望给出详细源代码
2
求助大神!线性表调用插入、删除等子函数的C语言主函数(用switch函数)怎么写?
1
数据结构线性表求助,数据结构萨尼书上的
2
一道C++的题,好像是对应的数据类型不对,但是实在是想不到如何修改好这个程序
0
求一个线性规划单纯形法求一般方程的C/C++程序。
1
整数线性表排序+反转的一个算法,采用C语言如何进行求解答?
0
一个和线性优化相关的试题,A Foldy but a Goody,采用C语言的正确解答
1
数据结构上的一个线性表的冲突的解决,是不是用哈希算法怎么采用C语言的实现方式
1
数组排序以后在线性表里二分搜索怎么用C语言的实现,看下面的问题怎么C语言实现
0
线性查找规划的算法,采用数据结构和C语言的实现的思路和方式???
0
线性递归序列的问题,递归函数倒推采用C语言的解法
0
一个多变量的线性规划的问题,采用C语言怎么做,不是思路很清楚了
0
线性规划问题,判断销售和广告的策略,采用C语言怎么实现这个问题的解答
0
线性表实现的区域策略算法问题,优化的算法用C语言开发编程的思路