借鉴博客： https://www.cnblogs.com/Howe-Young/p/4911992.html
https://www.cnblogs.com/bianjunting/p/10829212.html
借鉴视频：https://www.bilibili.com/video/BV1CC4y1a7kD?from=search&seid=17813568887618384754
一，定义
权值第 2 小的生成树。
广义上 次小生成树 可以和 最小生成树 权值一样
严格上 次小生成树 不能和 最小生成树 权值一样
二，前提知识
1，最小瓶颈生成树
① 定义： 给出加权无向图，求一棵生成树，使得最大边权值尽可能小
② 算法：从一个空图开始，按照权值从小到大的顺序依次加入各条边，则图第一次连通时，
该图的最小生成树就是最小瓶颈生成树。
③ 结论：由 Kruskal 算法求出的 最小生成树 即为 最小瓶颈生成树
2，最小瓶颈路
① 定义：给出加权无向图的两个结点 u 和 v，求出从 u 到 v 的一条路径，使得路径上的最长边尽量短。
② 算法：用 Kruskal 算法求出最小生成树，则树上 u 到 v 的路径就是我们要找的路径，路径上的最长边就是答案
③ 反证法：假设该路径 不是 最小生成树上的路径，则原图 u 到 v上必然存在一条路径，满足 两条路径不一样
且 原图上的路径的最长边 必然小于 最小生成树的最长边 ，这与 Kruskal 算法违背，则假设不成立，算法得证。
3，每对节点间的最小瓶颈路
给出加权无向图，求每两个结点 u 和 v 之间的最小瓶颈路 的最大边长 f( u,v )
解法 ①：先求出 最小生成树，用 DFS 遍历这个树，当访问一个节点时 u 时，考虑所有已经访问过的 结点 x ，
更新 f(x,u) = max(f(x,v),w(v,u))，其中 v 是 u 的父结点，每个 f(u,v) 只需要常数时间计算，因此时间复杂度为 O(n2)。
这里 将路径 x->u 分成两部分，
一是 x->v , 这里 f(x,v), 代表 x->v 路径上的最大边长，
一是 v->u , 这里 w(v,u),代表 边 v-u 的权值，
这两部分中的较大值自然就是 路径 x->u 中的最大边权值。
易得，当 x,u 代表的只有一条边时，f(x,u) 应该等于 w(v,u)，所以 f() 应该 初始化为最小值或者 0
解法 ②：用树上倍增的方法，统计每个点到 2的 j 次方 层祖先的最大距离
4，可行交换与临集
① T 为图G 的一棵生成树，对于非树边a 和 树边b，插入 边a 并且删除 边b 的操作记为 （+a,-b）
如果 T+a-b 仍然是 一棵生成树，称（+a,-b）是一个可行交换
② 由 T 进行一次 可行交换 后得到的 新生成树 的集合 称为 T的临集
③ 定理：次小生成树在最小生成树的临集中
粗略证明：因为 最小生成树 已然是最小代价的边权和，所以每次多一条边不一样，则代价必然增加，所以只改变一条边是代价最小的方法了，
大概吧 ε=ε=ε=ε=ε=ε=┌(;￣◇￣)┘
三，算法
算法 ①：次小生成树 不会与 最小生成树相同，因此可以枚举 最小生成树 中的一条边，将 该边 认为不会在 次小生成树 中出现，
然后在剩下的边里，求一次 最小生成树。注意 最小生成树只有 n-1 条边，所以只需要枚举 n-1 次。
这种算法 需要求 n 次最小生成树，时间复杂度挺大的，不推荐。
算法 ②：
1.先求出来最小生成树。在求 最小生成树 的时候一并将 最小生成树任意两点之间路径当中的权值最大的那一条 求出来。
2.尝试添加最小生成树外的每一条边，删除上面找到的边。其中的权值最小的就是次小生成树。
why?
原来 最小生成树加入一条边 (为什么是一条边呢？见上面的临集) 之后一定构成了回路，所以如果说 加入了边 ij , 此时 i 到 j 有两条路，这两条路构成一个回路，
要想构成生成树的话，必然删除这条回路上的边，要想和原来不一样且最小，则必然要删除原先 最小生成树上 i 到 j 路径中的最大边。
四，代码
Prim
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> #define inf 0x3f3f3f3f #define MIN(x,y) (x<y?x:y) #define MAX(x,y) (x>y?x:y) #define mem(a,b) memset(a,b,sizeof(a)) #define N 105 int a[N][N]; //邻接矩阵存图 int f[N][N]; //表示最小生成树中 i 到 j 的最大边权 int used[N][N]; // TE ，最小生成树的边集 int p[N]; // 路径 int dis[N]; // 集合 u 到 i 的最短距离 bool vis[N]; // 标记集合 u 的点 int n, m; // m 是边数， n 是点数 void init() { mem(a, 0x3f); mem(p, 0); mem(vis, 0); mem(dis, 0x3f); mem(used, 0); mem(f, 0); } int prim() // 求 最小生成树 { int s = 1; dis[1] = 0, vis[s] = 1, p[s] = 0; int sum = 0; for (int i = 1; i < n; i++) // 边数 为点数减一 { for (int j = 1; j <= n; j++) // 更新距离，标记起点 { if (vis[j] == 0 && dis[j] > a[s][j]) { dis[j] = a[s][j]; p[j] = s; } } int min = inf; for (int j = 1; j <= n; j++) // 找到 最小的那条边 { if (vis[j] == 0 && dis[j] < min) { min = dis[j]; s = j; } } if (min == inf) return -1; vis[s] = 1; used[s][p[s]] = used[p[s]][s] = 1; // TE sum += min; for (int j = 1; j <= n; j++) // 多了这一段 { if (vis[j]) f[j][s] = f[s][j] = MAX(f[j][p[s]], a[p[s]][s]); // 这里 dis[j] == a[p[s]][s] } } return sum; } int smst(int minT) // 求 次小生成树 { int ans = inf; for (int i = 1; i <= n; i++) //枚举最小生成树之外的边 { for (int j = i + 1; j <= n; j++) { if (a[i][j] != inf && !used[i][j]) ans = MIN(ans, minT + a[i][j] - f[i][j]); } } if (ans == inf) return -1; return ans; } int main(void) { int t; scanf("%d", &t); while (t--) { init(); scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int u, v, w; scanf("%d %d %d", &u, &v, &w); a[u][v] = a[v][u] = w; } int minT = prim(); // 最小生成树 if (minT == -1) puts("Not Unique!"); else { int secT = smst(minT); // 次小生成树 if (secT == minT) printf("Not Unique! "); else printf("%d ", minT); } } system("pause"); return 0; }
Kruskal
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<vector> #include<algorithm>] using namespace std; #define N 111 #define inf 0x3f3f3f3f #define MIN(x,y) (x<y?x:y) int p[N], f[N][N]; int n, m; vector<int> g[N]; struct edge { int from, to, w; int vis; // 标记 }e[123456]; int cmp(const edge &a, const edge &b) { return a.w < b.w; } int find(int x) { if (x != p[x]) p[x] = find(p[x]); return p[x]; } int join(int x, int y) { x = find(x), y = find(y); if (x == y) return 0; x = p[y]; return 1; } void init() { for (int i = 1; i <= n; i++) { g[i].clear(); g[i].push_back(i); p[i] = i; } } int Kruskal() { sort(e + 1, e + 1 + m, cmp); init(); int sum = 0, cnt = 0; for (int i = 1; i <= m; i++) { if (cnt == n - 1) break; int x = find(e[i].from), y = find(e[i].to); if (x != y) { cnt++; e[i].vis = 1; sum += e[i].w; int lx = g[x].size(), ly = g[y].size(); for (int j = 0; j < lx; j++) { for (int k = 0; k < ly; k++) f[g[x][j]][g[y][k]] = f[g[y][k]][g[x][j]] = e[i].w; } p[x] = y; for (int j = 0; j < lx; j++) { g[y].push_back(g[x][j]); } } } return sum; } int smst(int minT) { int sum = inf; for (int i = 1; i <= m; i++) { if (e[i].vis == 0) sum = MIN(sum, minT + e[i].w - f[e[i].from][e[i].to]); } return sum; } int main(void) { int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d%d", &e[i].from, &e[i].to, &e[i].w); e[i].vis = 0; } int minT = Kruskal(); int secT = smst(minT); if (secT != minT) printf("%d ", minT); else puts("Not Unique!"); } system("pause"); return 0; }
=========== ========= ======== ======= ======= ===== ==== === == =
高凉村妇盼郎归情歌
百里寻夫到天光 又到徐闻与海康
走尽花街和柳巷 谁知夫在鸡婆床
二八鸡婆巧梳妆 洞房夜夜换新郎
一双玉臂千人枕 半点朱唇万客尝
装成一身娇体态 扮做一副假心肠
迎来送往知多少 惯作相思泪两行
一生悲欢恨怨间 劝郎戒嫖把家还
一觉扬州梦应醒 为妻待郎情无限。