思路：
Prim：
这道题目中有重边
Prim可以先加一个sec数组来保存重边的次小边，这样不会影响到最小生成树，在算次小生成树时要同时判断次小边（不需判断是否在MST中）
Kruskal：
Kruskal对重边就很友好了，不用考虑
原理是这样的：我们先找最小生成树并用used标记好哪些边是MST的边，然后我们暴力遍历每一条MST边被删去的情况，如果还能生成MST就找出这些MST最小的，这棵MST就是次小生成树
Prim代码：
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
const int N = 200+5;
const int INF = 0x3f3f3f3f;
using namespace std;
int n,m,p[N],Case = 1;
int mp[N][N],sec[N][N],dis[N],x[N],y[N];
int pre[N];
bool vis[N];
int Max[N][N]; //最大权值边
bool is[N][N]; //是否在MST中
void init(){
int a,b,c;
scanf("%d%d",&n,&m);
memset(mp,INF,sizeof(mp));
memset(sec,INF,sizeof(sec));
for(int i = 1;i <= m;i++){
scanf("%d%d%d",&a,&b,&c);
if(c < mp[a][b]){
sec[a][b] = sec[b][a] = min(mp[a][b],sec[a][b]); //保存次小边
mp[a][b] = mp[b][a] = c;
}
else{
sec[a][b] = sec[b][a] = min(c,sec[a][b]);
}
}
memset(vis,false,sizeof(vis));
vis[1] = true;
for(int i = 2;i <= n;i++){
dis[i] = mp[i][1];
pre[i] = 1;
}
}
void Prim(){
int mincost = 0;
memset(Max,0,sizeof(Max));
memset(is,false,sizeof(is));
for(int i = 1;i <= n - 1;i++){
int MIN = INF;
int point = -1;
for(int j = 1;j <= n;j++){
if(!vis[j] && dis[j] < MIN){
MIN = dis[j];
point = j;
}
}
if(point == -1){
printf("Case #%d : No way
",Case++);
return;
}
vis[point] = true;
mincost += MIN;
is[point][pre[point]] = is[pre[point]][point] = true;
for(int j = 1;j <= n;j++){
if(vis[j] && j != point){
Max[j][point] = Max[point][j] = max(Max[pre[point]][j],dis[point]);
}
if(!vis[j] && dis[j] > mp[j][point]){
pre[j] = point;
dis[j] = mp[j][point];
}
}
}
int seccost = INF,flag = 0;
for(int i = 1;i <= n;i++){
for(int j = 1;j < i;j++){
if(mp[i][j] != INF && !is[i][j]){
flag = 1;
seccost = min(seccost,mincost - Max[i][j] + mp[i][j]);
}
if(sec[i][j] != INF){
flag = 1;
seccost = min(seccost,mincost - Max[i][j] + sec[i][j]);
}
}
}
if(!flag) printf("Case #%d : No second way
",Case++);
else printf("Case #%d : %d
",Case++,seccost);
}
int main() {
int T;
scanf("%d",&T);
while(T--){
init();
Prim();
}
return 0;
}
Kruskal代码：
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
const int N = 200+5;
const int INF = 0x3f3f3f3f;
using namespace std;
struct edge{
int u,v,w;
}e[N];
bool cmp(edge a,edge b){
return a.w < b.w;
}
int f[N],used[N];
int Case = 1;
int Find(int x){
return f[x] == x? x : f[x] = Find(f[x]);
}
void Kruskal(){
int n,m,a,b,c;
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
scanf("%d%d%d",&a,&b,&c);
e[i].u = a;
e[i].v = b;
e[i].w = c;
}
sort(e+1,e+m+1,cmp);
for(int i = 0;i <= n;i++) f[i] = i;
int cnt = 0,tot = 0;
for(int i = 1;i <= m;i++){
int fx = Find(e[i].u);
int fy = Find(e[i].v);
if(fx != fy){
f[fx] = fy;
cnt++;
used[tot++] = i;
}
if(cnt == n - 1) break;
}
if(cnt < n - 1){
printf("Case #%d : No way
",Case++);
return;
}
//次小生成树
int seccost = INF;
for(int i = 0;i < tot;i++){
for(int j = 0;j <= n;j++) f[j] = j;
int num = 0,cost = 0;
for(int j = 1;j <= m;j++){
if(j == used[i]) continue; //删边
int fx = Find(e[j].u);
int fy = Find(e[j].v);
if(fx != fy){
f[fx] = fy;
num++;
cost += e[j].w;
}
if(num == n - 1) break;
}
if(num == n-1) seccost = min(seccost,cost);
}
if(seccost == INF) printf("Case #%d : No second way
",Case++);
else printf("Case #%d : %d
",Case++,seccost);
}
int main() {
int T;
scanf("%d",&T);
while(T--){
Kruskal();
}
return 0;
}