这次是在图里面求严格次小生成树
#include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn=1e5+10; const int M=3e5+10; const int INF=0x3fffffff; typedef long long LL; typedef unsigned long long ull; /* https://blog.csdn.net/regina8023/article/details/44814899 https://blog.csdn.net/YYHS_WSF/article/details/82842355 求出最小生成树，枚举每一条非树边，用它取代掉环上最大的边最优。 那么相当于求两点到lca的最大边权，直接倍增做。 但是要注意是严格最小生成树，那么这条非树边与环上最大边相同时可能取代掉的是环上的次大边，那么倍增的时候多维护一个严格次大的边即可。 */ int n,m; struct node{ int u,v,wei; }ed[M]; queue q; struct edge{ int to,next,w; }e[M*2]; struct ma{ int a,b; //分别是 最大、次大 }g[maxn][21],p; int head[maxn],dep[maxn],f[maxn][21],fa[maxn]; //后两个：深度，倍增数组 int vis[M]; bool cmp(node a,node b){ return a.weiy.a) x.b=max(y.a,x.b); //b记录的是次大 ，这三行都是在更新次大 else if(x.a=0;i--){ if(dep[f[x][i]]>=deep) { updat(p,g[x][i]); x=f[x][i]; } } } void getlca(int x,int y){ p.a=p.b=-INF; if(dep[x]>dep[y]) swap(x,y); mov(y,dep[x]); //先移动到同一层 if(x==y) return; for(int i=20;i>=0;i--){ if(f[x][i]!=f[y][i]){ updat(p,g[x][i]); updat(p,g[y][i]); //找到替换的那条边严格最大边 x=f[x][i]; y=f[y][i]; } } updat(p,g[x][0]); updat(p,g[y][0]); } int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d %d %d",&ed[i].u,&ed[i].v,&ed[i].wei); } for(int i=1;i<=n;i++) fa[i]=i; kru(); //先求出最小生成树的权值 build(); //用非树边去更新倍增数组，g[][].a g[][].b ST(); LL ans=(LL)1e15; //这个要设置的足够大 for(int i=1;i<=m;i++){ if(!vis[i]){ //用非树边建立 getlca(ed[i].u,ed[i].v); if(p.a==ed[i].wei){ //最大便与其相等 ans=min(ans,mst+ed[i].wei-p.b); } else ans=min(ans,mst+ed[i].wei-p.a); } } printf("%lld\n",ans); return 0; }