网站建设推广优化公司_店铺首页设计步骤_优化近义词_站长之家网站查询

次小生成树算法详解

次小生成树问题是图论中的一个经典问题，其目标是在给定图的基础上，找到除了最小生成树（MST）以外权值最小的生成树。以下是对次小生成树算法及其相关问题的详细总结和解答。

1. 次小生成树问题概述

定义

• 最小生成树（MST）：一个无向图中，使所有节点连通且边权值之和最小的树。
• 次小生成树（SMST）：在所有不同于最小生成树的生成树中，权值次小的生成树。

目标

1. 构建最小生成树 $T$。
2. 在 $T$ 的基础上，通过加入某条非树边并替换树中的某条边，计算生成次小生成树的权值。

2. 算法思路

2.1 使用 Kruskal 算法构建 MST

• Kruskal 算法是一种基于边权值排序的最小生成树算法。
• 步骤：
  1. 按权值升序排列所有边。
  2. 使用并查集动态维护节点连通性。
  3. 遍历边列表，将不构成环的边加入生成树。
• 结果：
  • 构建 $T$ 的同时，标记哪些边是树边（used = true），哪些是非树边。

2.2 非树边的处理

• 非树边是构造次小生成树的关键，因为加入非树边会在 $T$ 中形成一个环。
• 在环中需要删除一条边，以确保生成树的性质。
• 删除哪条边取决于非树边的权值 $w$ 与环中树边的最大权值 $\text{max\_weight}$ 和次大权值 $\text{second\_max\_weight}$。

2.3 次小生成树的生成逻辑

1. 遍历所有非树边 $(a,b,w)$：
   • 加入 $w$ 后，计算 $a$ 到 $b$ 的路径上的最大权值和次大权值。
2. 比较非树边 $w$ 的权值：
   • 如果 $w>\text{max\_weight}$，替换最大权值边：
     $$\text{SMST 权值}=\text{MST 权值}+w-\text{max\_weight}$$

• 如果 $\text{second\_max\_weight}<w\le \text{max\_weight}$，替换次大权值边：
  $$\text{SMST 权值}=\text{MST 权值}+w-\text{second\_max\_weight}$$
• 如果 $w\le \text{second\_max\_weight}$，无法形成更优的次小生成树。

3. 关键技术点解析

3.1 Kruskal 算法的实现

LL kruskal() {sort(edge, edge + m);  // 按权值升序排列for (int i = 1; i <= n; i++) p[i] = i;  // 初始化并查集LL res = 0;for (int i = 0; i < m; i++) {int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;if (a != b) {  // 不在同一集合，加入生成树p[a] = b;res += w;edge[i].used = true;  // 标记为树边}}return res;  // 返回 MST 权值
}

3.2 倍增法预处理最大值和次大值

• 倍增法用于快速找到两节点路径上的最大权值和次大权值，结合 $O(\log N)$ 的 LCA 查询，可以高效解决环中边的替换问题。

最大值和次大值的递归计算：

d1[j][k] = max(d1[j][k-1], d1[fa[j][k-1]]);
d2[j][k] = 次大值 ({d1[j][k-1], d2[j][k-1], d1[fa[j][k-1]], d2[fa[j][k-1]]});

3.3 处理非树边形成的环

• 对每条非树边 $(a,b,w)$，计算环中路径的最大和次大权值：

LL lca(int a, int b, int w) {if (depth[a] < depth[b]) swap(a, b);static int distance[100];int cnt = 0;// 将 a 提升到与 b 相同深度for (int k = 16; k >= 0; k--) {if (depth[fa[a][k]] >= depth[b]) {distance[cnt++] = d1[a][k];distance[cnt++] = d2[a][k];a = fa[a][k];}}// 若 a 和 b 不相等，则继续往上跳if (a != b) {for (int k = 16; k >= 0; k--) {if (fa[a][k] != fa[b][k]) {distance[cnt++] = d1[a][k];distance[cnt++] = d2[a][k];distance[cnt++] = d1[b][k];distance[cnt++] = d2[b][k];a = fa[a][k];b = fa[b][k];}}distance[cnt++] = d1[a][0];distance[cnt++] = d1[b][0];}// 找到路径中最大值和次大值int dist1 = -INF, dist2 = -INF;for (int i = 0; i < cnt; i++) {if (distance[i] > dist1) dist2 = dist1, dist1 = distance[i];else if (distance[i] != dist1 && distance[i] > dist2) dist2 = distance[i];}// 判断非树边替换的情况if (w > dist1) return w - dist1;else if (w > dist2) return w - dist2;else return INF;
}

4. 示例

输入图

边列表：

(1, 2, 10)
(1, 3, 12)
(2, 3, 14)  // 非树边
(3, 4, 8)

步骤

1. 使用 Kruskal 算法，构建 MST：

   • MST 边集：$(1,2,10),(1,3,12),(3,4,8)$，权值和 $\text{sum}=30$。

2. 非树边处理：

   • $(2,3,14)$：形成环 $[10,12,14]$。
   • 最大值：$\text{dist1}=14$，次大值：$\text{dist2}=12$。
   • 判断：
     • $w=14$，无法替换环中最大值和次大值。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;typedef long long LL;const int N = 100010, M = 300010, INF = 0x3f3f3f3f;int n, m;
struct Edge {int a, b, w;bool used;bool operator< (const Edge& t) const {return w < t.w;}
}edge[M];int p[N];
int h[N], e[M], w[M], ne[M], idx;
int depth[N], fa[N][17], d1[N][17], d2[N][17];
int q[N];void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
}LL kruskal() {for (int i = 1; i <= n; ++i) p[i] = i;sort(edge, edge + m);LL res = 0;for (int i = 0; i < m; ++i) {int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;if (a != b) {p[a] = b;res += w;edge[i].used = true;}}return res;
}void build() {memset(h, -1, sizeof h);for (int i = 0; i < m; ++i) {if (edge[i].used) {int a = edge[i].a, b = edge[i].b, w = edge[i].w;add(a, b, w), add(b, a, w);}}
}void bfs() {memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;q[0] = 1;int hh = 0, tt = 0;while (hh <= tt) {int t = q[hh++];for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q[++tt] = j;fa[j][0] = t;d1[j][0] = w[i], d2[j][0] = -INF;for (int k = 1; k <= 16; ++k) {int anc = fa[j][k-1];fa[j][k] = fa[anc][k-1];int distance[4] = {d1[j][k-1], d2[j][k-1], d1[anc][k-1], d2[anc][k-1]};d1[j][k] = d2[j][k] = -INF;for (int u = 0; u < 4; ++u) {int d = distance[u];if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d; }}}}}
} int lca(int a, int b, int w) {static int distance[N * 2];int cnt = 0;if (depth[a] < depth[b]) swap(a, b);for (int k = 16; k >= 0; --k) {if (depth[fa[a][k]] >= depth[b]) {distance[cnt++] = d1[a][k];distance[cnt++] = d2[a][k];a = fa[a][k];}}if (a != b) {for (int k = 16; k >= 0; --k) {if (fa[a][k] != fa[b][k]) {distance[cnt++] = d1[a][k];distance[cnt++] = d2[a][k];distance[cnt++] = d1[b][k];distance[cnt++] = d2[b][k];a = fa[a][k], b = fa[b][k];}}distance[cnt++] = d1[a][0];distance[cnt++] = d1[b][0];}int dist1 = -INF, dist2 = -INF;for (int i = 0; i < cnt; ++i) {int d = distance[i];if (d > dist1) dist2 = dist1, dist1 = d;else if(d != dist1 && d > dist2) dist2 = d;}if (w > dist1) return w - dist1;if (w > dist2) return w - dist2;return INF;
}int main() {scanf("%d%d", &n, &m);for (int i = 0; i < m; ++i) {int a, b, c;scanf("%d%d%d", &a, &b, &c);edge[i] = {a, b, c};}LL sum = kruskal();build();bfs();LL res = 1e18;for (int i = 0; i < m; ++i) {if (!edge[i].used) {int a = edge[i].a, b = edge[i].b, w = edge[i].w;res = min(res, sum + lca(a, b, w));}}printf("%lld\n", res);return 0;
}

5. 总结

1. 算法流程：

   • 使用 Kruskal 构建 MST。
   • 利用倍增法和 LCA 查询非树边引入环后的替换关系。
   • 遍历非树边，更新次小生成树权值。

2. 复杂度：

   • Kruskal：$O(M\log M)$。
   • 倍增法预处理：$O(N\log N)$。
   • 查询环：$O(M\log N)$。

3. 应用场景：

   • 次小生成树问题常用于网络设计的冗余路径规划和故障恢复。

   • 次小生成树算法详解

     次小生成树问题是图论中的一个经典问题，其目标是在给定图的基础上，找到除了最小生成树（MST）以外权值最小的生成树。以下是对次小生成树算法及其相关问题的详细总结和解答。

     1. 次小生成树问题概述

     定义

     • 最小生成树（MST）：一个无向图中，使所有节点连通且边权值之和最小的树。
     • 次小生成树（SMST）：在所有不同于最小生成树的生成树中，权值次小的生成树。

     目标

     1. 构建最小生成树 $T$。
     2. 在 $T$ 的基础上，通过加入某条非树边并替换树中的某条边，计算生成次小生成树的权值。

     2. 算法思路

     2.1 使用 Kruskal 算法构建 MST

     • Kruskal 算法是一种基于边权值排序的最小生成树算法。
     • 步骤：
       1. 按权值升序排列所有边。
       2. 使用并查集动态维护节点连通性。
       3. 遍历边列表，将不构成环的边加入生成树。
     • 结果：
       • 构建 $T$ 的同时，标记哪些边是树边（used = true），哪些是非树边。

     2.2 非树边的处理

     • 非树边是构造次小生成树的关键，因为加入非树边会在 $T$ 中形成一个环。
     • 在环中需要删除一条边，以确保生成树的性质。
     • 删除哪条边取决于非树边的权值 $w$ 与环中树边的最大权值 $\text{max\_weight}$ 和次大权值 $\text{second\_max\_weight}$。

     2.3 次小生成树的生成逻辑

     1. 遍历所有非树边 $(a,b,w)$：
        • 加入 $w$ 后，计算 $a$ 到 $b$ 的路径上的最大权值和次大权值。
     2. 比较非树边 $w$ 的权值：
        • 如果 $w>\text{max\_weight}$，替换最大权值边：
          $$\text{SMST 权值}=\text{MST 权值}+w-\text{max\_weight}$$
     • 如果 $\text{second\_max\_weight}<w\le \text{max\_weight}$，替换次大权值边：
       $$\text{SMST 权值}=\text{MST 权值}+w-\text{second\_max\_weight}$$
     • 如果 $w\le \text{second\_max\_weight}$，无法形成更优的次小生成树。

     3. 关键技术点解析

     3.1 Kruskal 算法的实现

     LL kruskal() {sort(edge, edge + m);  // 按权值升序排列for (int i = 1; i <= n; i++) p[i] = i;  // 初始化并查集LL res = 0;for (int i = 0; i < m; i++) {int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;if (a != b) {  // 不在同一集合，加入生成树p[a] = b;res += w;edge[i].used = true;  // 标记为树边}}return res;  // 返回 MST 权值
     }
     

     3.2 倍增法预处理最大值和次大值

     • 倍增法用于快速找到两节点路径上的最大权值和次大权值，结合 $O(\log N)$ 的 LCA 查询，可以高效解决环中边的替换问题。

     最大值和次大值的递归计算：

     d1[j][k] = max(d1[j][k-1], d1[fa[j][k-1]]);
     d2[j][k] = 次大值 ({d1[j][k-1], d2[j][k-1], d1[fa[j][k-1]], d2[fa[j][k-1]]});
     

     3.3 处理非树边形成的环

     • 对每条非树边 $(a,b,w)$，计算环中路径的最大和次大权值：

     LL lca(int a, int b, int w) {if (depth[a] < depth[b]) swap(a, b);static int distance[100];int cnt = 0;// 将 a 提升到与 b 相同深度for (int k = 16; k >= 0; k--) {if (depth[fa[a][k]] >= depth[b]) {distance[cnt++] = d1[a][k];distance[cnt++] = d2[a][k];a = fa[a][k];}}// 若 a 和 b 不相等，则继续往上跳if (a != b) {for (int k = 16; k >= 0; k--) {if (fa[a][k] != fa[b][k]) {distance[cnt++] = d1[a][k];distance[cnt++] = d2[a][k];distance[cnt++] = d1[b][k];distance[cnt++] = d2[b][k];a = fa[a][k];b = fa[b][k];}}distance[cnt++] = d1[a][0];distance[cnt++] = d1[b][0];}// 找到路径中最大值和次大值int dist1 = -INF, dist2 = -INF;for (int i = 0; i < cnt; i++) {if (distance[i] > dist1) dist2 = dist1, dist1 = distance[i];else if (distance[i] != dist1 && distance[i] > dist2) dist2 = distance[i];}// 判断非树边替换的情况if (w > dist1) return w - dist1;else if (w > dist2) return w - dist2;else return INF;
     }
     

     4. 示例

     输入图

     边列表：

     (1, 2, 10)
     (1, 3, 12)
     (2, 3, 14)  // 非树边
     (3, 4, 8)
     

     步骤

     1. 使用 Kruskal 算法，构建 MST：

        • MST 边集：$(1,2,10),(1,3,12),(3,4,8)$，权值和 $\text{sum}=30$。

     2. 非树边处理：

        • $(2,3,14)$：形成环 $[10,12,14]$。
        • 最大值：$\text{dist1}=14$，次大值：$\text{dist2}=12$。
        • 判断：
          • $w=14$，无法替换环中最大值和次大值。

     #include <iostream>
     #include <cstring>
     #include <algorithm>
     #include <cstdio>using namespace std;typedef long long LL;const int N = 100010, M = 300010, INF = 0x3f3f3f3f;int n, m;
     struct Edge {int a, b, w;bool used;bool operator< (const Edge& t) const {return w < t.w;}
     }edge[M];int p[N];
     int h[N], e[M], w[M], ne[M], idx;
     int depth[N], fa[N][17], d1[N][17], d2[N][17];
     int q[N];void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
     }int find(int x) {if (p[x] != x) p[x] = find(p[x]);return p[x];
     }LL kruskal() {for (int i = 1; i <= n; ++i) p[i] = i;sort(edge, edge + m);LL res = 0;for (int i = 0; i < m; ++i) {int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;if (a != b) {p[a] = b;res += w;edge[i].used = true;}}return res;
     }void build() {memset(h, -1, sizeof h);for (int i = 0; i < m; ++i) {if (edge[i].used) {int a = edge[i].a, b = edge[i].b, w = edge[i].w;add(a, b, w), add(b, a, w);}}
     }void bfs() {memset(depth, 0x3f, sizeof depth);depth[0] = 0, depth[1] = 1;q[0] = 1;int hh = 0, tt = 0;while (hh <= tt) {int t = q[hh++];for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (depth[j] > depth[t] + 1) {depth[j] = depth[t] + 1;q[++tt] = j;fa[j][0] = t;d1[j][0] = w[i], d2[j][0] = -INF;for (int k = 1; k <= 16; ++k) {int anc = fa[j][k-1];fa[j][k] = fa[anc][k-1];int distance[4] = {d1[j][k-1], d2[j][k-1], d1[anc][k-1], d2[anc][k-1]};d1[j][k] = d2[j][k] = -INF;for (int u = 0; u < 4; ++u) {int d = distance[u];if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d; }}}}}
     } int lca(int a, int b, int w) {static int distance[N * 2];int cnt = 0;if (depth[a] < depth[b]) swap(a, b);for (int k = 16; k >= 0; --k) {if (depth[fa[a][k]] >= depth[b]) {distance[cnt++] = d1[a][k];distance[cnt++] = d2[a][k];a = fa[a][k];}}if (a != b) {for (int k = 16; k >= 0; --k) {if (fa[a][k] != fa[b][k]) {distance[cnt++] = d1[a][k];distance[cnt++] = d2[a][k];distance[cnt++] = d1[b][k];distance[cnt++] = d2[b][k];a = fa[a][k], b = fa[b][k];}}distance[cnt++] = d1[a][0];distance[cnt++] = d1[b][0];}int dist1 = -INF, dist2 = -INF;for (int i = 0; i < cnt; ++i) {int d = distance[i];if (d > dist1) dist2 = dist1, dist1 = d;else if(d != dist1 && d > dist2) dist2 = d;}if (w > dist1) return w - dist1;if (w > dist2) return w - dist2;return INF;
     }int main() {scanf("%d%d", &n, &m);for (int i = 0; i < m; ++i) {int a, b, c;scanf("%d%d%d", &a, &b, &c);edge[i] = {a, b, c};}LL sum = kruskal();build();bfs();LL res = 1e18;for (int i = 0; i < m; ++i) {if (!edge[i].used) {int a = edge[i].a, b = edge[i].b, w = edge[i].w;res = min(res, sum + lca(a, b, w));}}printf("%lld\n", res);return 0;
     }

     5. 总结

     1. 算法流程：

        • 使用 Kruskal 构建 MST。
        • 利用倍增法和 LCA 查询非树边引入环后的替换关系。
        • 遍历非树边，更新次小生成树权值。

     2. 复杂度：

        • Kruskal：$O(M\log M)$。
        • 倍增法预处理：$O(N\log N)$。
        • 查询环：$O(M\log N)$。

     3. 应用场景：

        • 次小生成树问题常用于网络设计的冗余路径规划和故障恢复。