1888: 最大生成树

内存限制:128 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:3 通过:0

题目描述

最大生成树:对无向连通图的生成树,各边的权值总和称为生成树的权,权最大的生成树称为最大生成树。给定一个无向连通图,输出其最大生成树的权值。

输入格式

输入文件中包含多个测试数据,输入文件第1行为一个整数T,代表输入文件中有T个测试数据。接下来是T个测试数据。每个测试数据描述了一个无向连通图,其中第1行为两个整数n和m,n为顶点数,m为边数,2≤n≤10,1≤m≤45,这n个顶点的序号为1~n;接下来有m行,每行描述了一条边,格式为:u v w,分别表示这条边的两个顶点及边上的权值。

输出格式

对每个无向连通图,输出其最大生成树的权值。

输入样例 复制

7 9
1 2 28
1 6 10
2 3 16
2 7 14
3 4 12
4 5 22
4 7 18
5 6 25
5 7 24

输出样例 复制

129