最小生成树与次小生成树(65%)
2026-02-04 16:01:11
发布于：浙江
10阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
long long inf=0x7f7f7f7f7f7f7f7f;
//kruskal{
const int N=200007;
const int M=200007;
struct edge{
int nxt,to,val;
}e[N<<1];
int h[N],cnt;
void add(int u,int v,int w){
e[++cnt].nxt=h[u];
e[cnt].to=v;
e[cnt].val=w;
h[u]=cnt;
}
struct edge1{
int u,v,w;
bool used;
}e1[M];
int n,m,fa[N];
long long ans0=0;
bool cmp(edge1 a,edge1 b){
return a.w<b.w;
}
int find(int x){
if(x!=fa[x]) return fa[x]=find(fa[x]);
return x;
}
void kruskal(){
sort(e1+1,e1+m+1,cmp);
for(int i=1;i<=m;++i){
int u=find(e1[i].u),v=find(e1[i].v);
if(u==v) continue;
ans0+=e1[i].w;
add(e1[i].u,e1[i].v,e1[i].w);
add(e1[i].v,e1[i].u,e1[i].w);
e1[i].used=1;fa[v]=u;
}
}
//}
int f[N][20],mx[N][20],mx2[N][20],dep[N];
void dfs(int u){
dep[u]=dep[f[u][0]]+1;
for(int i=1;i<=18;i++){
f[u][i]=f[f[u][i-1]][i-1];
if(mx[u][i-1]==mx[f[u][i-1]][i-1]){
mx[u][i]=mx[u][i-1];
mx2[u][i]=max(mx2[f[u][i-1]][i-1],mx2[u][i-1]);
}
if(mx[u][i-1]>mx[f[u][i-1]][i-1]){
mx[u][i]=mx[u][i-1];
mx2[u][i]=max(mx[f[u][i-1]][i-1],mx2[u][i-1]);
}
if(mx[u][i-1]<mx[f[u][i-1]][i-1]){
mx[u][i]=mx[f[u][i-1]][i-1];
mx2[u][i]=max(mx[u][i-1],mx2[f[u][i-1]][i-1]);
}
}
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].val;
if(v==f[u][0]) continue;
f[v][0]=u;
mx[v][0]=w;
dfs(v);
}
}
int lca(int u,int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=18;i>=0;--i)
if(dep[u]-dep[v]>=(1<<i))
u=f[u][i];
if(u==v) return u;
for(int i=18;i>=0;--i)
if(f[u][i]!=f[v][i]){
u=f[u][i];v=f[v][i];
}
return f[u][0];
}
long long cal(int u,int v,int w){
int l=lca(u,v);
int nmx=0,nmx2=0;
for(int i=18;i>=0;--i){
if(dep[f[u][i]]>=dep[l]){
if(nmx==mx[u][i]) nmx2=max(mx2[u][i],nmx2);
if(nmx>mx[u][i]) nmx2=max(mx[u][i],nmx2);
if(nmx<mx[u][i]){nmx2=max(mx2[u][i],nmx);nmx=mx[u][i];}
u=f[u][i];
}
if(dep[f[v][i]]>=dep[l]){
if(nmx==mx[v][i]) nmx2=max(mx2[v][i],nmx2);
if(nmx>mx[v][i]) nmx2=max(mx[v][i],nmx2);
if(nmx<mx[v][i]){nmx2=max(mx2[v][i],nmx);nmx=mx[v][i];}
v=f[v][i];
}
}
if(w!=nmx) return ans0-nmx+w;
if(nmx2) return ans0-nmx2+w;
return inf;
}
int main(){
cin>>n>>m;
if(m==0){cout<<"-1 -1";return 0;}
for(int i=1;i<=m;++i){
++cnt;cin>>e1[cnt].u>>e1[cnt].v>>e1[cnt].w;
if(e1[cnt].u==e1[cnt].v) --cnt;
}
for(int i=1;i<=n;++i) fa[i]=i;
kruskal();
dfs(1);
long long ans=inf;
for(int i=1;i<=m;++i)
if(!e1[i].used)
ans=min(cal(e1[i].u,e1[i].v,e1[i].w),ans);
if(ans0>inf/2) cout<<"-1 -1";
else if(ans>inf/2) cout<<ans0<<" -1";
else cout<<ans0<<' '<<ans;
return 0;
}
这里空空如也
有帮助，赞一个