我用的小小的次小生成树模板

次小生成树的生成分为两种，一种是带重边的，一种是不带重边的~~；

首先是不带重边的，就可以用prim来做

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 105;
int Map[maxn][maxn];//存图；
int Max[maxn][maxn];//a到b的最大边权
bool used[maxn][maxn];//判断是否加入生成树；
int pre[maxn];//最小生成树终端为s时的前驱是谁
int dis[maxn];//在已存的点集中，到各个点的最短边；
bool vis[maxn];
int n, m;
void init()
{
	for (int s = 1; s <= n; s++)
	{
		for (int w = 1; w <= n; w++)
		{
			if (s == w)
				Map[s][w] = 0;
			else
				Map[s][w] = inf;
		}
	}
}
void read()
{
	int a, b, c;
	for (int s = 0; s < m; s++)
	{
		scanf("%d%d%d", &a, &b, &c);
		Map[b][a] = Map[a][b] = min(Map[a][b], c);
	}
}
int prim()
{
	int ans = 0;//最小生成
	memset(vis, 0, sizeof(vis));
	memset(Max, 0, sizeof(Max));
	memset(used, 0, sizeof(used));
	for (int s = 2; s <= n; s++)//把1加入初始化点集；
	{
		dis[s] = Map[1][s];
		pre[s] = 1;
	}
	pre[1] = 0;
	dis[1] = 0;
	vis[1] = 1;
	for (int s = 2; s <= n; s++)//找到最小的边
	{
		int min_ans = inf, key;
		for (int s = 1; s <= n; s++)
		{
			if (!vis[s] && min_ans > dis[s])
			{
				min_ans = dis[s];
				key = s;
			}
		}
		if (min_ans == inf)return -1;
		ans += min_ans;
		vis[key] = 1;
		used[key][pre[key]] = used[pre[key]][key] = 1;
		for (int s = 1; s <= n; s++)
		{
			if(vis[s]&&s!=key)Max[s][key]=Max[key][s]=max(Max[s][pre[key]], dis[key]);
			if (!vis[s] && dis[s] > Map[key][s])//更新dis
			{
				dis[s] = Map[key][s];
				pre[s] = key;
			}
		}
	}
	return ans;
}
int sec_mst(int min_ans)
{
	int ans = inf;
	for (int s = 1; s <= n; s++)
	{
		for (int w = s + 1; w <= n; w++)
		{
			if (Map[s][w] != inf && !used[s][w])
			{
				ans = min(ans, min_ans + Map[s][w] - Max[s][w]);
			}
		}
	}
	if (ans == inf)return -2;
	return ans;
}
int main()
{
	int te;
	scanf("%d", &te);
	while (te--)
	{
		scanf("%d%d", &n, &m);
		init();
		read();
		int fir_ans=prim();
		if (fir_ans == -1)
		{
			cout << "没最小生成树" << endl;
			continue;
		}	
		int sec_ans = sec_mst(fir_ans);
		if (sec_ans == -2)
		{
			cout << "没次小生成树" << endl;
		}
		else
		{
			cout << sec_ans << endl;
		}
	}
}

其次如果存在重边的话~~就需要直接暴力来做了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
struct node
{
	int u, v, cost;
}e[121211];
int pre[121211];
int edge[112211];
bool cmp(struct node a, struct node b)
{
	return a.cost<b.cost;
}
int Find(int a)
{
	if (a != pre[a])
	{
		pre[a] = Find(pre[a]);
	}
	return pre[a];
}
int top;
int Kru()
{
	int num = 0;
	for (int i = 0; i <= n; i++)
		pre[i] = i;
	for (int i = 0; i<m; i++)
	{
		int x = Find(pre[e[i].u]);
		int y = Find(pre[e[i].v]);
		if (x != y)
		{
			num += e[i].cost;
			edge[++top] = i;
			pre[y] = x;
		}
	}
	int k = 0;
	for (int i = 1; i <= n; i++)
	{
		if (pre[i] == i)
			k++;
	}
	if (k == 1)
		return num;
	else
		return INF;
}
//int top;
int Kru2(int xx)
{
	int num = 0;
	for (int i = 0; i <= n; i++)
		pre[i] = i;
	for (int i = 0; i<m; i++)
	{
		if (i == xx)
			continue;
		int x = Find(pre[e[i].u]);
		int y = Find(pre[e[i].v]);
		if (x != y)
		{
			num += e[i].cost;
			//         edge[++top] = i;
			pre[y] = x;
		}
	}
	int k = 0;
	for (int i = 1; i <= n; i++)
	{
		if (pre[i] == i)
			k++;
	}
	if (k == 1)
		return num;
	else
		return INF;
}
int main()
{
	int T;
	scanf("%d", &T);
	for (int t = 1; t <= T; t++)
	{
		scanf("%d %d", &n, &m);
		for (int i = 0; i<m; i++)
		{
			scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].cost);
		}
		sort(e, e + m, cmp);
		top = -1;
		int ans1 = Kru(), ans2 = INF;
		for (int i = 0; i <= top; i++)
		{
			int x = edge[i];
			ans2 = min(ans2, Kru2(x));
		}
		if (ans1 == INF)
			printf("Case #%d : No way\n", t);
		else if (ans2 == INF)
			printf("Case #%d : No second way\n", t);
		else
			printf("Case #%d : %d\n", t, ans2);//次小生成树的长短~
	}
	return 0;
}