思路：
Prim：
这道题目中有重边
Prim可以先加一个sec数组来保存重边的次小边，这样不会影响到最小生成树，在算次小生成树时要同时判断次小边（不需判断是否在MST中）
Kruskal：
Kruskal对重边就很友好了，不用考虑
原理是这样的：我们先找最小生成树并用used标记好哪些边是MST的边，然后我们暴力遍历每一条MST边被删去的情况，如果还能生成MST就找出这些MST最小的，这棵MST就是次小生成树
Prim代码：
#include#include #include #include #include #include #include #include #include #include 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#include #include #include #include #include #include #include #include #include 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;}