1 问题
设最小生成树的总权值为
并在所有满足这个条件的生成树中,令
换成另一棵同权 MST 不算严格次小;原图也可能没有严格次小生成树,例如原图本身就是一棵树,或所有生成树的总权值都相同。
本篇沿用 最小生成树 的 Kruskal 建树,以及 瓶颈路 的树上倍增查询。
2 加边与删边
固定一棵 MST
要重新得到生成树,必须删去环上的一条原树边
若要求
为了让新权值尽量小,应删除路径上严格小于
例如三角形边权为
- 删去原来的
,仍为 ,只得到另一棵 MST。 - 删去
,得到 ,才是严格次小。
因此,不能总是删除路径最大边,也不能在非树边等于最大值时直接放弃。
3 单次换边
固定任意一棵 MST,若严格次小生成树存在,则至少有一棵严格次小生成树,可以从这棵 MST 删去一条边、加入一条边得到。
这里说“至少有一棵”,不要求每棵严格次小树都只与固定的 MST 相差一条边。
3.1 证明
设固定 MST 为
两边的边数相同。使用一个树的交换引理:可以将
由于
又因为配对恰好覆盖所有不同边,
必有某个
注意,这些是分别从同一棵
交换引理的证明
这部分使用 Hall 匹配定理,可在理解算法后阅读。
先收缩
构造一个二分图:左侧为
任取左侧边集
一个含
Hall 定理说明:若左侧任意子集的邻居数都不少于自身,就存在覆盖左侧的匹配。两侧大小相同,这个匹配给出所需的一一配对。
这个引理只要求每对边单独交换后,
4 最大与严格次大
非树边
设路径上两个最大的不同边权为
- 若
,删去 ,候选为 。 - 若
,只能删去严格次大值 ,候选为 。 - 若第二种情况中不存在
,这条非树边不能产生严格增加的候选。
例如路径权值为
5 倍增维护
5.1 信息合并
用 Info{mx1,mx2} 保存两个最大不同值。插入一个候选权值
void add_value(Info &a, ll x) {
if (x == NEG) return;
if (x > a.mx1) {
a.mx2 = a.mx1;
a.mx1 = x;
} else if (x < a.mx1 && x > a.mx2) {
a.mx2 = x;
}
}
等于最大值的数不能进入第二位。单条边的信息为 {w,NEG},空段为 {NEG,NEG}。
合并两段路径,只需将它们各自的两个候选合并。某个被舍弃的值,在原段内已有两个更大的不同值,因此不可能进入合并后的前两大。
5.2 祖先表与查询
定义:
up[u][j]:向上 步的祖先。 mx1[u][j]:这段路径的最大边权。mx2[u][j]:这段路径的严格次大边权。
预处理时,合并前后两段
关键仍是先合并当前段,再移动顶点。两点最后停在 LCA 的两个孩子时,还要补上它们到 LCA 的两条父边。
6 示例
仍用基础篇的五点八边图,固定边集
枚举四条非树边:
| 非树边 | 路径最大值 |
严格次大值 |
删除边权 | 新权值 |
|---|---|---|---|---|
第一条非树边等于路径最大值,但仍能删除权值
7 代码
采用 luogu P4180: [BJWC2010] 严格次小生成树 的边列表格式。先输入 u v w,输出严格次小总权值。
原题保证严格次小存在。下面的模板额外约定:原图不连通,或不存在严格次小树时,输出
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;
const int maxm = 300000 + 5;
struct Edge {
int u, v, id;
ll w;
};
Edge e[maxm];
int fa[maxn], sz[maxn];
void init(int n) {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
sz[i] = 1;
}
}
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
bool unite(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (sz[fx] < sz[fy]) swap(fx, fy);
fa[fy] = fx;
sz[fx] += sz[fy];
return true;
}
bool cmp(const Edge &a, const Edge &b) {
if (a.w != b.w) return a.w < b.w;
return a.id < b.id; // 同权时按输入顺序,便于与正文示例核对
}
const int LOG = 18;
const ll INF = 1LL << 62;
const ll NEG = -(1LL << 62); // 不存在第二种边权,且小于模板允许的所有边权
struct TreeEdge {
int to;
ll w;
};
struct Info {
ll mx1, mx2; // 最大值、严格小于最大值的次大值
};
vector<TreeEdge> g[maxn];
bool in_mst[maxm]; // 按原始边编号标记,排序后仍能区分重边
int dep[maxn], up[maxn][LOG], que[maxn];
ll mx1[maxn][LOG], mx2[maxn][LOG];
void add_value(Info &a, ll x) {
if (x == NEG) return;
if (x > a.mx1) {
a.mx2 = a.mx1;
a.mx1 = x;
} else if (x < a.mx1 && x > a.mx2) {
a.mx2 = x; // 与最大值相等的数不能成为严格次大值
}
}
Info merge_info(Info a, const Info &b) {
add_value(a, b.mx1);
add_value(a, b.mx2);
return a;
}
Info segment(int u, int j) {
return {mx1[u][j], mx2[u][j]};
}
bool build_mst(int n, int m, ll &total) {
init(n);
for (int u = 1; u <= n; ++u) g[u].clear();
fill(in_mst, in_mst + m, false);
sort(e, e + m, cmp);
total = 0;
int selected = 0;
for (int i = 0; i < m && selected < n - 1; ++i) {
if (!unite(e[i].u, e[i].v)) continue;
in_mst[e[i].id] = true;
total += e[i].w;
++selected;
g[e[i].u].push_back({e[i].v, e[i].w});
g[e[i].v].push_back({e[i].u, e[i].w});
}
return selected == n - 1;
}
void build_lifting(int n) {
for (int u = 0; u <= n; ++u) {
dep[u] = 0;
for (int j = 0; j < LOG; ++j) {
up[u][j] = 0;
mx1[u][j] = mx2[u][j] = NEG;
}
}
// 用数组队列遍历树,链形 MST 也不会造成递归栈过深。
int head = 0, tail = 0;
que[tail++] = 1;
dep[1] = 1;
while (head < tail) {
int u = que[head++];
for (auto [v, w] : g[u]) {
if (v == up[u][0]) continue;
dep[v] = dep[u] + 1;
up[v][0] = u;
mx1[v][0] = w;
for (int j = 1; j < LOG; ++j) {
int p = up[v][j - 1];
up[v][j] = up[p][j - 1];
Info a = merge_info(segment(v, j - 1), segment(p, j - 1));
mx1[v][j] = a.mx1;
mx2[v][j] = a.mx2;
}
que[tail++] = v;
}
}
}
Info path_info(int u, int v) {
Info answer{NEG, NEG};
if (dep[u] < dep[v]) swap(u, v);
int diff = dep[u] - dep[v];
for (int j = LOG - 1; j >= 0; --j) {
if (diff >> j & 1) {
answer = merge_info(answer, segment(u, j));
u = up[u][j];
}
}
if (u == v) return answer;
for (int j = LOG - 1; j >= 0; --j) {
if (up[u][j] != up[v][j]) {
answer = merge_info(answer, segment(u, j));
answer = merge_info(answer, segment(v, j));
u = up[u][j];
v = up[v][j];
}
}
answer = merge_info(answer, segment(u, 0));
return merge_info(answer, segment(v, 0));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> e[i].u >> e[i].v >> e[i].w;
e[i].id = i;
}
ll total;
if (!build_mst(n, m, total)) {
cout << -1 << '\n';
return 0;
}
build_lifting(n);
ll answer = INF;
for (int i = 0; i < m; ++i) {
const Edge &edge = e[i];
if (in_mst[edge.id] || edge.u == edge.v) continue;
Info a = path_info(edge.u, edge.v);
ll removed = NEG;
if (edge.w > a.mx1) removed = a.mx1;
else if (edge.w == a.mx1) removed = a.mx2;
if (removed != NEG) {
answer = min(answer, total + edge.w - removed);
}
}
// 原题保证严格次小生成树存在;本模板额外约定无解时输出 -1。
if (answer == INF) cout << -1 << '\n';
else cout << answer << '\n';
return 0;
}
使用基础篇的输入:
5 8
1 2 1
2 3 2
1 3 2
3 4 4
2 4 5
4 5 3
3 5 6
1 5 8
输出:
11
模板先用 Kruskal 建 MST,按原始边编号标记是否被选中,再建立树上倍增表。排序后仍使用原编号访问标记,重边也能分别识别。
树的遍历采用数组队列,避免链形 MST 造成递归栈过深。并查集的 find 仍使用路径压缩与按大小合并,树高受到控制。
8 正确性
单次换边性质保证,全部严格次小解中,至少有一个能通过本算法枚举的方式产生。
对固定非树边,加入后形成唯一环;要恢复生成树,只能删除环上的原树边。严格增加要求删边权小于新边权,取其中最大的一个,就得到以这条新边完成交换时的最优候选。
MST 性质保证新边权不小于路径最大值,因此“最大值或严格次大值”覆盖了全部所需情况。倍增查询正确合并路径信息,所有非树边的候选取最小,便得到严格次小权值。
9 复杂度与边界
Kruskal 需要排序与并查集操作,倍增预处理为
空间为
- 模板支持
、 , LOG=18覆盖所需层数。 - 允许零权、负权与重边,本系列按
使用。权值、总和与候选均用 ll。 NEG表示不存在某种边权,INF表示尚无候选。不能用作为不存在标记。 - 不存在 MST 用布尔值判断,不能用
total==-1判断;负权图中也可能是合法总权值。 - 自环不能成为生成树边,枚举非树边时也要跳过,不能对空路径做换边。
- 若路径上只有一种边权,严格次大值不存在。不能把另一次出现的最大值放进第二位。
- 最小生成树不唯一,不代表没有严格次小;但也不能保证一定存在严格次小。例如等权三角形只有同权生成树。
10 练习
10.1 边界数据
分别求下面三张图的 MST 权值与严格次小权值:
- 三角形边权
。 - 三角形边权
。 - 三角形边权
。
参考结果
- MST 为
,严格次小为 。 - MST 为
,不存在严格次小。 - MST 为
,严格次小为 。仍需删除严格次大值,不能使用零初值。
10.2 推荐题目
| 层次 | 题目 | 训练内容 |
|---|---|---|
| 严格次小 | luogu P4180: [BJWC2010] 严格次小生成树 | 完整实现最大、严格次大值的倍增合并,处理自环与同权边。 |
| 换边变体 | codeforces 609E | 对每条边求必须包含它时的最小生成树权值;此题允许结果等于 MST,非树边直接删除路径最大边。点数可达 |
完成本篇后,可以进一步研究 MST 唯一性与必须包含某条边的最优代价;这些问题都建立在“非树边与树上路径形成环”的关系上。
11 参考
- Donald 与 Tobey:A Generalised Exchange Theorem for Matroid Bases:独立交换的一一配对及 Hall 定理背景。
12 相关题解
暂无相关题解