题意:给定一张(n)个点(m)条边的无向图,求无向图的严格次小生成树.(n<=1e5,m<=3e5.)
分析:先(kruskal)求出图的最小生成树,设边权之和为(sum.)我们把在最小生成树中的(n-1)条边先加入图中,对新图(这棵最小生成树)(dfs),预处理出(f[i][j],maxn[i][j],minn[i][j])分别表示(i)的(2^j)级祖先,(i)到其(2^j)级祖先的路径上的最大边权,(i)到其(2^j)级祖先的路径上的次大边权.
然后对于剩下的(m-(n-1))条边,我们每次枚举一条边,设该边两个端点分别为(x,y),权值为(z),找到(x->y)路径上的最大边权(maxx),则答案可以更新为(ans=min(ans,sum-maxx+z)),相当于删去这条边权最大的边,加入我们当前枚举的这条边,从而保证严格次小.
(long) (long)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline ll read(){
ll x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=1e5+5;
const int M=3e5+5;
ll n,m,sum,ans,maxn[N][25],minn[N][25];
ll fa[N],bj[M],dep[N],f[N][25];
ll tot,head[N],nxt[M],to[M],w[M];
struct edge{ll x,y,z;}a[M];
inline bool cmp(edge x,edge y){return x.z<y.z;}
inline int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
inline void add(int a,int b,ll c){
nxt[++tot]=head[a];head[a]=tot;
to[tot]=b;w[tot]=c;
}
inline void kruskal(){//最小生成树模板
sort(a+1,a+m+1,cmp);int k=0;//边权从小到达排序
for(int i=1;i<=n;++i)fa[i]=i;//初始化并查集
for(int i=1;i<=m;++i){
int x=find(a[i].x),y=find(a[i].y);
if(x==y)continue;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);//重新建图
sum+=a[i].z;bj[i]=1;//把这条边标记为加入了最小生成树
fa[x]=y;if(++k==n-1)break;
}
}
inline void dfs(int u,int fa){//LCA的预处理
for(int j=1;j<=20;++j){
f[u][j]=f[f[u][j-1]][j-1];
maxn[u][j]=max(maxn[u][j-1],maxn[f[u][j-1]][j-1]);
minn[u][j]=max(minn[u][j-1],minn[f[u][j-1]][j-1]);
if(maxn[u][j-1]>maxn[f[u][j-1]][j-1])minn[u][j]=max(minn[u][j],maxn[f[u][j-1]][j-1]);
else if(maxn[u][j-1]<maxn[f[u][j-1]][j-1])minn[u][j]=max(minn[u][j],maxn[u][j-1]);
}
for(ll i=head[u];i;i=nxt[i]){
ll v=to[i];if(v==fa)continue;
f[v][0]=u;maxn[v][0]=w[i];minn[v][0]=-1e18;
dep[v]=dep[u]+1;dfs(v,u);
}
}
inline ll LCA(ll x,ll y){
if(dep[x]<dep[y])swap(x,y);
for(int j=20;j>=0;--j)
if(dep[f[x][j]]>=dep[y])x=f[x][j];
if(x==y)return x;
for(int j=20;j>=0;--j)
if(f[x][j]!=f[y][j])x=f[x][j],y=f[y][j];
return f[x][0];
}
inline ll query(ll x,ll y,ll z){
ll Ans=-1e18;
for(int j=20;j>=0;--j)
if(dep[f[x][j]]>=dep[y]){
if(z!=maxn[x][j])Ans=max(Ans,maxn[x][j]);
else Ans=max(Ans,minn[x][j]);
x=f[x][j];
}
return Ans;
}
int main(){
n=read();m=read();
for(int i=1;i<=m;++i)a[i].x=read(),a[i].y=read(),a[i].z=read();
kruskal();dfs(1,0);ans=1e18;
for(int i=1;i<=m;++i)
if(!bj[i]){//枚举没有加入最小生成树的边
ll x=a[i].x,y=a[i].y,z=a[i].z,lca=LCA(x,y);
ll max1=query(x,lca,z),max2=query(y,lca,z);//先分别找两个点到lca的最大值
ans=min(ans,sum-max(max1,max2)+z);//两者中取最大值加入图中
}
printf("%lld
",ans);
return 0;
}
那些初始化赋值,一定要赋值为超级大,(1e9)都会挂.