大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168625.html原文链接：https://javaforall.net
