// 如果不重边 可用prim算法 在最普通prim基础上添加used[][] 和 path[][] 数组,used[i][j]表示i到j这条无向边是否添加在(第一次求得的)最小生成树中, path[i][j]表示i到j(可理解为这条树链)中边的最大值。
次小树 可理解为i--j这条边没有用到,现在选取它作为生成树的一条边,这样i->j就形成一个环,所以需要删除原本i->j上最长的边，这样才可能是次小树，因此枚举i,j 计算MST
1 /* 2 * @Promlem: 3 * @Time Limit: ms 4 * @Memory Limit: k 5 * @Author: pupil-XJ 6 * @Date: 2019-10-21 22:54:50 7 * @LastEditTime: 2019-10-21 23:32:16 8 */ 9 #include<cstdio> 10 #include<cstring> 11 #include<cmath> 12 #include<iostream> 13 #include<string> 14 #include<algorithm> 15 #include<vector> 16 #include<queue> 17 #include<stack> 18 #include<set> 19 #include<map> 20 #define rep(i, n) for(int i=0;i!=n;++i) 21 #define per(i, n) for(int i=n-1;i>=0;--i) 22 #define Rep(i, sta, n) for(int i=sta;i!=n;++i) 23 #define rep1(i, n) for(int i=1;i<=n;++i) 24 #define per1(i, n) for(int i=n;i>=1;--i) 25 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i) 26 #define L k<<1 27 #define R k<<1|1 28 #define mid (tree[k].l+tree[k].r)>>1 29 using namespace std; 30 const int INF = 0x3f3f3f3f; 31 typedef long long ll; 32 33 inline int read() { 34 char c=getchar();int x=0,f=1; 35 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 36 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 37 return x*f; 38 } 39 // ----------------------------------------------------- 40 const int MAXN = 100+5; 41 42 int n, m; 43 int G[MAXN][MAXN]; 44 int vis[MAXN], dis[MAXN], pre[MAXN], used[MAXN][MAXN], path[MAXN][MAXN]; 45 46 inline int prim() { 47 int ans = 0; 48 rep1(i, n) { 49 dis[i] = G[i][1]; 50 pre[i] = 1; vis[i] = 0; 51 rep1(j, n) used[i][j] = path[i][j] = 0; 52 } 53 vis[1] = 1; 54 rep(i, n-1) { 55 int minn = INF; 56 int t; 57 rep1(j, n) { 58 if(!vis[j] && dis[j] < minn) { 59 minn = dis[j]; 60 t = j; 61 } 62 } 63 vis[t] = 1; 64 ans += minn; 65 used[t][pre[t]] = used[pre[t]][t] = 1; 66 rep1(j, n) { 67 if(!vis[j] && dis[j] > G[t][j]) { 68 pre[j] = t; 69 dis[j] = G[t][j]; 70 } 71 if(vis[j] && j != t) { 72 path[j][t] = path[t][j] = max(path[j][pre[t]], minn); 73 } 74 } 75 } 76 return ans; 77 } 78 79 int main() { 80 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 81 int T = read(); 82 while(T--) { 83 n = read(); m = read(); 84 rep1(i, n) rep1(j, n) G[i][j] = INF; 85 int s, e, v; 86 rep(i, m) { 87 s = read(); e = read(); v = read(); 88 G[s][e] = G[e][s] = v; 89 } 90 int sum = prim(); 91 int ans = INF; 92 rep1(i, n) Rep1(j, i+1, n) { 93 if(G[i][j] != INF && !used[i][j]) { 94 ans = min(ans, sum-path[i][j]+G[i][j]); 95 } 96 } 97 cout << sum << " " << ans << " "; 98 } 99 return 0; 100 }
// 如果重边 就用kruskal算法, 边的结构体中添加 int used, del; used 记录第一次最小生成树是否用了此边(为了之后枚举删除第一次用到的边); del表示是否删除该边.每次删除边之后算MST,相当于找一个边替代它,替代完之后才有可能是次小树
//因此代码很好得出
1 /* 2 * @Promlem: 3 * @Time Limit: ms 4 * @Memory Limit: k 5 * @Author: pupil-XJ 6 * @Date: 2019-10-21 23:48:51 7 * @LastEditTime: 2019-10-22 00:41:56 8 */ 9 #include<cstdio> 10 #include<cstring> 11 #include<cmath> 12 #include<iostream> 13 #include<string> 14 #include<algorithm> 15 #include<vector> 16 #include<queue> 17 #include<stack> 18 #include<set> 19 #include<map> 20 #define rep(i, n) for(int i=0;i!=n;++i) 21 #define per(i, n) for(int i=n-1;i>=0;--i) 22 #define Rep(i, sta, n) for(int i=sta;i!=n;++i) 23 #define rep1(i, n) for(int i=1;i<=n;++i) 24 #define per1(i, n) for(int i=n;i>=1;--i) 25 #define Rep1(i, sta, n) for(int i=sta;i<=n;++i) 26 #define L k<<1 27 #define R k<<1|1 28 #define mid (tree[k].l+tree[k].r)>>1 29 using namespace std; 30 const int INF = 0x3f3f3f3f; 31 typedef long long ll; 32 33 inline int read() { 34 char c=getchar();int x=0,f=1; 35 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 36 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 37 return x*f; 38 } 39 // ----------------------------------------------------- 40 const int MAXN = 100+5; 41 const int MAXM = 200+5; 42 43 struct node { 44 int s, e, w; 45 int used, del; 46 bool operator < (const node &a) const { 47 return w < a.w; 48 } 49 } edge[MAXM]; 50 51 int n, m; 52 int fa[MAXN]; 53 bool First; 54 55 inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } 56 57 inline int krustra() { 58 int sum = 0; 59 int cnt = 1; 60 rep1(i, n) fa[i] = i; 61 rep(i, m) { 62 if(cnt == n) break; 63 if(edge[i].del) continue; 64 int xf = find(edge[i].s); 65 int yf = find(edge[i].e); 66 if(xf != yf) { 67 fa[xf] = yf; 68 sum += edge[i].w; 69 ++cnt; 70 if(First) edge[i].used = 1; 71 } 72 } 73 if(cnt != n) return -1; 74 return sum; 75 } 76 77 int main() { 78 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 79 int T = read(); 80 int cnt = 1; 81 while(T--) { 82 n = read(); m = read(); 83 int s, e, v; 84 rep(i, m) { 85 edge[i].s = read(); 86 edge[i].e = read(); 87 edge[i].w = read(); 88 edge[i].used = edge[i].del = 0; 89 } 90 cout << "Case #" << cnt++ << " : "; 91 sort(edge, edge+m); 92 First = true; 93 int sum = krustra(); 94 First = false; 95 if(sum == -1) cout << "No way "; 96 else { 97 int ans = INF; 98 rep(i, m) { 99 if(edge[i].used) { 100 edge[i].del = 1; 101 int t = krustra(); 102 edge[i].del = 0; 103 if(t != -1) ans = min(ans, t); 104 } 105 } 106 if(ans == INF) cout << "No second way "; 107 else cout << ans << " "; 108 } 109 } 110 return 0; 111 }