最小生成树的个数_最小生成树的两种算法

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一张 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

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 3 * 3e5 + 10;
const int maxbit = 20;
typedef long long ll;
int f[N][maxbit],d1[N][maxbit],d2[N][maxbit],height[N];
struct Edge{ 

int u,v,w,next;
bool f;
bool operator<(const Edge a)const{ 

return w < a.w;
}
}edge[M];
int head[N],cnt;
int n,m;
int fa[N];
int Find(int x){ 

return fa[x] = (fa[x] == x ? x : Find(fa[x]));
}
void add(int u,int v,int w){ 

edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
void dfs(int u,int fa,int d,int w){ 

f[u][0] = fa;
height[u] = d;
d1[u][0] = w,d2[u][0] = 0;
for(int i = 1;i <= maxbit - 1;i ++){ 

f[u][i] = f[f[u][i - 1]][i - 1];
d1[u][i] = max(d1[u][i - 1],d1[f[u][i - 1]][i - 1]);
if(d1[u][i - 1] == d1[f[u][i - 1]][i - 1])
d2[u][i] = max(d2[u][i - 1],d2[f[u][i - 1]][i - 1]);
if(d1[u][i - 1] > d1[f[u][i - 1]][i - 1])
d2[u][i] = max(d1[f[u][i - 1]][i - 1],d2[u][i - 1]);
else d2[u][i] = max(d1[u][i - 1],d2[f[u][i - 1]][i - 1]);
}
for(int i = head[u];~i;i = edge[i].next){ 

int v = edge[i].v,ww = edge[i].w;
if(v == fa)continue;
dfs(v,u,d + 1,ww);
}
}
int lca(int x,int y,int &a,int &b){ 

a = b = 0;
if(height[x] < height[y])swap(x,y);
for(int i = maxbit - 1;i >= 0;i --){ 

if(height[f[x][i]] >= height[y]){ 

if(d1[x][i] > a)b = a,a = d1[x][i];
else if(d1[x][i] != a && d1[x][i] > b)b = d1[x][i]; 
if(d2[x][i] > a)b = a,a = d2[x][i];
else if(d2[x][i] != a && d2[x][i] > b)b = d2[x][i];
x = f[x][i];
}
}
if(x == y)return x;
for(int i = maxbit - 1;i >= 0;i --){ 

if(f[x][i] != f[y][i]){ 

int aa = d1[x][i],bb = d2[x][i],cc = d1[y][i],dd = d2[y][i];
if(aa > a)b = a,a = aa;
else if(aa != a && aa > b)b = aa;
if(bb > a)b = a,a = bb;
else if(bb != a && bb > b)b = bb; 
if(cc > a)b = a,a = cc;
else if(cc != a && cc > b)b = cc; 
if(dd > a)b = a,a = dd;
else if(dd != a && dd > b)b = dd; 
x = f[x][i],y = f[y][i];
}
}
int aa = d1[x][0],bb = d2[x][0],cc = d1[y][0],dd = d2[y][0];
if(aa > a)b = a,a = aa;
else if(aa != a && aa > b)b = aa;
if(bb > a)b = a,a = bb;
else if(bb != a && bb > b)b = bb; 
if(cc > a)b = a,a = cc;
else if(cc != a && cc > b)b = cc; 
if(dd > a)b = a,a = dd;
else if(dd != a && dd > b)b = dd; 
return f[x][0];
}
int main(){ 

memset(head,-1,sizeof head);
cin>>n>>m;
int x,y,w;
for(int i = 0;i < m;i ++){ 

cin>>x>>y>>w;
edge[i].u = x,edge[i].v = y,edge[i].w = w;
edge[i].f = false;
}
cnt = m;
sort(edge,edge + m);
for(int i = 0;i <= n;i ++)fa[i] = i;
ll res = 0;
for(int i = 0;i < m;i ++){ 

int a = Find(edge[i].u),b = Find(edge[i].v),w = edge[i].w;
if(a != b){ 

fa[a] = b;
edge[i].f = true;
add(edge[i].u,edge[i].v,w),add(edge[i].v,edge[i].u,w);
res += w;
}
}
dfs(1,0,1,0);
int xx,yy;
ll t = 0x3f3f3f3f3f3f3f3f;
for(int i = 0;i < m;i ++){ 

if(!edge[i].f){ 

int a = edge[i].u,b = edge[i].v,w = edge[i].w;
int aa = 0,bb = 0;
lca(a,b,aa,bb);
if(aa == w){ 

t = min(res + w - bb,t);
}
else t = min(res + w - aa,t);
}
}
cout<<t<<endl;
return 0;
}