洛谷题单指南-最小生成树-P4180 [BJWC2010] 严格次小生成树
原题链接：https://www.luogu.com.cn/problem/P4180
题意解读：求严格次小生成树。
解题思路：
一、定义
次小生成树是在一个连通图中，生成树中权值第二小的树。
严格次小生成树是指在一个连通图中，权值严格大于最小生成树且是所有生成树中权值次小的生成树。
二、定理
性质：如果严格次小生成树存在，则一定存在一棵严格次小生成树，它与最小生成树只有一条边不同。
证明：反证法
假设存在一棵严格次小生成树T’，它与最小生成树T至少有两条边不同。
将T的边从小到大进行排序，找到第一条不在T’中的边e。因为T是最小生成树，所以e的权值小于等于T’中对应替换边的权值（若e的权值大于对应替换边的权值，那么T’就不是次小生成树了，因为用e替换后会得到更小的生成树）。
考虑在T’中加入边e，这样会形成一个环。由于T是最小生成树，根据其性质，环上除e外的其他边权值都大于等于e的权值。
在这个环中选择一条边e’(e’!=e)）删除，使得T’仍然是生成树。如果e’的权值大于e的权值，那么新得到的生成树T’’的权值会小于T’的权值而大于T的权值，这与T’是严格次小生成树矛盾；如果有多条边不同但是除了1条边严格不同其余的长度是相等的，也就是其余的e’的权值等于e的权值，那么可以不断重复上述操作，直到T与T’只存在一条边不同。此时得到的生成树就是与最小生成树只有一条边不同的严格次小生成树。
也就是说，在最小生成树T的构建逻辑下，环上除了边e之外的其他边，不可能存在权值比e小的情况，否则在构建T的过程中，这些权值更小的边会被优先选取。所以环上除e外的其他边权值都大于等于e的权值。
综上，一定存在一棵严格次小生成树，它与最小生成树只有一条边不同。
补充证明：环上除e外的其他边权值都大于等于e的权值
我们可以从最小生成树的构建过程和其最优性来理解 “环上除e外的其他边权值都大于等于e的权值” 这一结论，以下是详细解释：
最小生成树的构建性质（以 Kruskal 算法为例）： Kruskal 算法构建最小生成树的过程是将图中的边按照权值从小到大排序，然后依次选取边加入到最小生成树中，且保证加入的边不会形成环。也就是说，在构建最小生成树T的过程中，每次选取的边都是当前能选的权值最小的边，并且不会使已选边构成环。
分析加入边e后形成的环： 假设边e是最小生成树T中的一条边，且不在严格次小生成树T’中。当把边e加入到T’中时会形成一个环（因为T’是生成树，加入一条额外的边必然会产生环）。
由于最小生成树T是通过不断选取当前最小权值边构建而成的，对于这个新形成的环(环上其他边跟边e一样可以连接两个独立连通块)来说，环上的边如果存在权值小于e的边，那么在构建T时，按照 Kruskal 算法的规则（优先选择权值小的边），就应该先选择这条权值小于e的边，而不是边e。
三、算法过程
有了以上的理论基础，我们可以通过以下方式求解严格次小生成树：
先求最小生成树，标识出最小生成树的每一条边；
枚举每一条非树边u->v，将其加入到最小生成树中，这时会形成一个环，在环上移除掉原属于最小生成树的一条最长的边，如果最长边与当前加入边相等，则需要移除次长边；
更新此时得到新的生成树的权值和答案。
问题的关键在于，如何在原最小生成树所有两点u->v路径上找到最长边、次长边？
方法1：枚举法（整体复杂度为O(n^2)，无法AC）
从每一个点u开始跑一遍DFS，在DFS中更新u到所有点的路径上的最长边、次长边。
方法2：倍增法（整体复杂度nlogn）
借助于LCA，定义fa[i][j]为i的第2^j个祖先节点，d1[i][j]为i到第2^j个祖先路径上的最长边，d2[i][j]为i到第2^j个祖先路径上的次长边
d1、d2初始化可以和父节点fa的初始化一起
fa[u][0] = p;
d1[u][0] = length; //u到第2^0个父节点路径的最长边
d2[u][0] = -INF; //u到第2^0个父节点路径的次长边，因为次长边不存在
for(int i = 1; i <= 16; i++)
{
int t = fa[u][i - 1];
fa[u][i] = fa[t][i - 1];
//找到两个2^(i-1)路径的最长边、次长边
//总的最长边就是所有边的最大值，总的次长边就是所有边的次大值
int nums[] = {d1[u][i - 1], d2[u][i - 1], d1[t][i - 1], d2[t][i - 1]};
int max1 = -INF, max2 = -INF;
for(int j = 0; j < 4; j++)
{
if(nums[j] > max1) max2 = max1, max1 = nums[j];
else if(nums[j] < max1 && nums[j] > max2) max2 = nums[j];
}
d1[u][i] = max1, d2[u][i] = max2;
}
要计算u->v路径上最长边，只需要在LCA算法过程中去记录每一段路径的最长边、次长边，最后枚举出总路径的最长边、次长边
int nums[2 * N], cnt = 0; //记录路径上所有区间的最长边、次长边
if(depth[u] < depth[v]) swap(u, v);
for(int i = 16; i >= 0; i--)
{
if(depth[fa[u][i]] >= depth[v])
{
nums[++cnt] = d1[u][i], nums[++cnt] = d2[u][i];
u = fa[u][i];
}
}
if(u != v)
{
for(int i = 16; i >= 0; i--)
{
if(fa[u][i] != fa[v][i])
{
nums[++cnt] = d1[u][i], nums[++cnt] = d2[u][i]; //u到lca(u,v)子节点的一段
nums[++cnt] = d1[v][i], nums[++cnt] = d2[v][i]; //v到lca(u,v)子节点的一段
u = fa[u][i], v = fa[v][i];
}
}
//最后一段
nums[++cnt] = d1[u][0], nums[++cnt] = d2[u][0];
nums[++cnt] = d1[v][0], nums[++cnt] = d2[v][0];
}
//在所有区间找最大边、次大边
int max1 = -INF, max2 = -INF;
for(int i = 1; i <= cnt; i++)
{
if(nums[i] > max1) max2 = max1, max1 = nums[i];
else if(nums[i] < max1 && nums[i] > max2) max2 = nums[i];
}
100分代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100005, M = 300005, INF = 0x3f3f3f3f;
struct Edge
{
int u, v, w;
bool intree; //标识该边在最小生成树中
bool operator < (const Edge &e) const
{
return w < e.w;
}
} edges[M];
int h[N], e[M], w[M], ne[M], idx; //邻接表
int p[N]; //并查集
int depth[N], fa[N][17], d1[N][17], d2[N][17]; //深度，父节点，最长边，次长边
int n, m;
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()
{
LL res = 0;
for(int i = 1; i <= n; i++) p[i] = i;
sort(edges + 1, edges + m + 1);
for(int i = 1; i <= m; i++)
{
int a = find(edges[i].u);
int b = find(edges[i].v);
if(a != b)
{
p[a] = b;
res += edges[i].w;
edges[i].intree = true; //标记树中节点
}
}
return res;
}
void build()
{
memset(h, -1, sizeof(h));
for(int i = 1; i <= m; i++)
{
if(edges[i].intree)
{
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
add(u, v, w), add(v, u, w);
}
}
}
void dfs(int u, int p, int length)
{
depth[u] = depth[p] + 1;
fa[u][0] = p;
d1[u][0] = length; //u到第2^0个父节点路径的最长边
d2[u][0] = -INF; //u到第2^0个父节点路径的次长边，因为次长边不存在
for(int i = 1; i <= 16; i++)
{
int t = fa[u][i - 1];
fa[u][i] = fa[t][i - 1];
//找到两个2^i-1路径的最长边、次长边
//总的最长边就是所有边的最大值，总的次长边就是所有边的次大值
int nums[] = {d1[u][i - 1], d2[u][i - 1], d1[t][i - 1], d2[t][i - 1]};
int max1 = -INF, max2 = -INF;
for(int j = 0; j < 4; j++)
{
if(nums[j] > max1) max2 = max1, max1 = nums[j];
else if(nums[j] < max1 && nums[j] > max2) max2 = nums[j];
}
d1[u][i] = max1, d2[u][i] = max2;
}
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if(v == p) continue;
dfs(v, u, w[i]);
}
}
int lca(int u, int v, int length)
{
int nums[2 * N], cnt = 0;
if(depth[u] < depth[v]) swap(u, v);
for(int i = 16; i >= 0; i--)
{
if(depth[fa[u][i]] >= depth[v])
{
nums[++cnt] = d1[u][i], nums[++cnt] = d2[u][i];
u = fa[u][i];
}
}
if(u != v)
{
for(int i = 16; i >= 0; i--)
{
if(fa[u][i] != fa[v][i])
{
nums[++cnt] = d1[u][i], nums[++cnt] = d2[u][i]; //u到lca(u,v)子节点的一段
nums[++cnt] = d1[v][i], nums[++cnt] = d2[v][i]; //v到lca(u,v)子节点的一段
u = fa[u][i], v = fa[v][i];
}
}
//最后一段
nums[++cnt] = d1[u][0], nums[++cnt] = d2[u][0];
nums[++cnt] = d1[v][0], nums[++cnt] = d2[v][0];
}
//在所有区间找最大边、次大边
int max1 = -INF, max2 = -INF;
for(int i = 1; i <= cnt; i++)
{
if(nums[i] > max1) max2 = max1, max1 = nums[i];
else if(nums[i] < max1 && nums[i] > max2) max2 = nums[i];
}
if(length > max1) return max1;
else if(length > max2) return max2;
else return -INF; //没有合适的替换边
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
cin >> edges[i].u >> edges[i].v >> edges[i].w;
//先跑一遍kruskal，求最小生成树
LL res = kruskal();
//基于最小生成树建图
build();
//初始化fa、d1、d2
dfs(1, 0, 0);
LL ans = 1e18;
//枚举非树边，替换原最小生成树中相同路径上的最长边或者次长边，更新答案
for(int i = 1; i <= m; i++)
{
if(!edges[i].intree)
{
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int x = lca(u, v, w); //通过lca算法过程，找到u->v路径上的最长边或者次长边
ans = min(ans, res + w - x);
}
}
cout << ans;
return 0;
}