Description
最小生成树大家都已经很了解，次小生成树就是图中构成的树的权值和第二小的树，此值也可能等于最小生成树的权值和，你的任务就是设计一个算法计算图的最小生成树。
Input
存在多组数据，第一行一个正整数t，表示有t组数据。
每组数据第一行有两个整数n和m（2<=n<=100），之后m行，每行三个正整数s，e，w，表示s到e的双向路的权值为w。
Output
输出次小生成树的值，如果不存在输出-1。
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
4
6
克鲁斯卡尔算法。
求一次是最小生成树，两次就是次小生成数了。
//Asimple
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <string>
#include <queue>
#define INF 100000
using namespace std;
const int maxn = ;
typedef long long ll ;
int fa[maxn];//并查集
int vis[maxn];//记录下标
int path;//记录最小生成树用到边的数量
int T, n, m;
typedef struct node{
int st;
int ed;
int w;
bool operator < (const node& A) const {
return w<A.w ;
}
}node;
//初始化
void init(){
//获取并查集的大小
int len = sizeof(fa)/sizeof(fa[]);
for(int i=; i<len; i++){
fa[i] = i;
}
}
//并查集的查找——查找父节点
int findfa(int x){
int pa;
if( x == fa[x] ) return x;
pa = findfa(fa[x]);
fa[x] = pa;
return pa;
}
//求最小生成树
int minTree(node *points, int m, int n)
{
init(); int i, count, flag, pa, pb; for (i = count = flag = path = ; i < m; i ++) {
pa = findfa(points[i].st);
pb = findfa(points[i].ed); if (pa != pb) {
vis[path ++] = i;
fa[pa] = pb;
count ++;
} if (count == n - ) {
flag = ;
break;
}
} return flag;
} // 求次小生成树
int secMinTree(node *points, int m, int n)
{
int i, j, min, tmp, pa, pb, count, flag; for (i = , min = INF; i < path; i ++) {
init(); // 求次小生成树
for (j = count = tmp = flag = ; j < m; j ++) {
if (j != vis[i]) {
pa = findfa(points[j].st);
pb = findfa(points[j].ed); if (pa != pb) {
count ++;
tmp += points[j].w;
fa[pa] = pb;
} if (count == n - ) {
flag = ;
break;
}
}
} if (flag && tmp < min) min = tmp;
} min = (min == INF) ? - : min; return min;
}
int main(){
node *p;
scanf("%d",&T);
while( T -- ){
scanf("%d %d",&n, &m);
p = (node *)malloc(sizeof(node) * m);
for(int i=; i<m; i++){
scanf("%d %d %d",&p[i].st,&p[i].ed,&p[i].w);
}
sort(p,p+m); int f = minTree(p,m,n); if( f == ){//无法生成最小生成树
printf("-1\n");
continue;
} else {
int Min = secMinTree(p,m,n);
printf("%d\n",Min);
}
//释放p
free(p);
}
return ;
}