思路：

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\n",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\n",Case++);

    else printf("Case #%d : %d\n",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\n",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\n",Case++);

    else printf("Case #%d : %d\n",Case++,seccost);

}

int main() {

    int T;

    scanf("%d",&T);

    while(T--){

        Kruskal();

    }

    return 0;

}