题目描述
给定一张 N
个点 M
条边的无向图,求无向图的严格次小生成树。
设最小生成树的边权之和为 sum
,严格次小生成树就是指边权之和大于 sum
的生成树中最小的一个。
输入格式
第一行包含两个整数 N
和 M
。
接下来 M
行,每行包含三个整数 x,y,z
,表示点 x
和点 y
之前存在一条边,边的权值为 z
。
输出格式
包含一行,仅一个数,表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)
数据范围
N≤105,M≤3×105
样例
输入样例:
5 6
1 2 1
1 3 2
2 4 3
3 5 4
3 4 3
4 5 6
输出样例:
11
算法1
本质上算法与1148.秘密的牛奶运输中是一样的,只是在计算dist[a][b]时我们借鉴了lca算法中的倍增法。
时间复杂度
这里的时间复杂度分析:
1. kruskal算法:nlog(n)
2. 初始化数组的总时间:nlog(n)
3. 枚举最小生成树邻集中的次小生成树:mlog(n)
经过分析这里的算法优于之前1148.秘密的牛奶运输中的n^2级别的暴力dfs算法
C++ 代码
# include <iostream>
# include <algorithm>
# include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 3e5 + 10, INF = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
struct Edge{
int a, b, w;
bool f; // 表示这条边是否已经使用过
bool operator <(const Edge &W) const{
return w < W.w;
}
}edges[M];
int depth[N], dist1[N][17], dist2[N][17], fa[N][17];
int n, m, p[N], q[N];
void add(int a, int b, int c){
e[idx] = b, ne[idx] = h[a], w[idx] = c, 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(edges, edges+m);
LL res = 0;
for (int i = 0; i < m; i++){
int a = find(edges[i].a), b= find(edges[i].b), c = edges[i].w;
if (a != b){
edges[i].f = true;
p[a] = b;
res += c;
}
}
return res;
}
void build(){
// 建立最小生成树的图
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++){
if (!edges[i].f) continue;
int a = edges[i].a, b = edges[i].b, c = edges[i].w;
// cout << "a " << a << " b " << b << endl;
add(a,b,c), add(b,a,c);
}
}
void bfs(){
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[1] = 1;
int hh = 0, tt = -1;
q[++tt] = 1;
int cnt = 0;
while (hh <= tt && cnt < 20){
int ver = q[hh++];
for (int i = h[ver]; ~i; i = ne[i]){
int j = e[i];
if (depth[j] > depth[ver] + w[i]){
depth[j] = depth[ver] + w[i];
q[++tt] =j;
depth[j] = depth[ver] + 1;
fa[j][0] = ver;
dist1[j][0] = w[i], dist2[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] = {dist1[j][k-1], dist2[j][k-1], dist1[anc][k-1], dist2[anc][k-1]};
dist1[j][k] = -INF, dist2[j][k] = -INF;
for (int u = 0; u < 4; u++){
int d = distance[u];
if (d > dist1[j][k]) dist2[j][k] = dist1[j][k], dist1[j][k] = d;
else if (d != dist1[j][k] && d > dist2[j][k]) dist2[j][k] = d;
}
}
}
}
}
}
int lca(int a, int b, int w){
static int distance[2*N];
int cnt = 0;
if (depth[a] < depth[b]) swap(a, b);
// 然后先把a跳到和b一样的深度
for (int k = 16; k >= 0; k--)
if (depth[fa[a][k]] >= depth[b]){
distance[cnt++] = dist1[a][k];
distance[cnt++] = dist2[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++] = dist1[a][k];
distance[cnt++] = dist2[a][k];
distance[cnt++] = dist1[b][k];
distance[cnt++] = dist2[b][k];
a = fa[a][k];
b = fa[b][k];
}
}
distance[cnt++] = dist1[a][0];
distance[cnt++] = dist1[b][0];
}
int d1 = -INF, d2 = -INF;
for (int i = 0; i < cnt; i++){
int d = distance[i] ;
if (d > d1) d2 = d1, d1 = d;
else if (d != d1 && d > d2) d2 = d;
}
if (w > d1) return w - d1;
if (w > d2) return w - d2;
return INF;
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) scanf("%d%d%d", &edges[i].a, &edges[i].b, &edges[i].w);
LL sum = kruskal();
build();
bfs();
LL res = 1e18;
for (int i = 0; i < m; i++){
if (!edges[i].f){
int a = edges[i].a, b = edges[i].b, c = edges[i].w;
res = min(res, sum + lca(a,b,c));
}
}
printf("%lld\n", res);
return 0;
}