次小生成树

一、总体思路

首先,我这一题的思路是倍增LCA+Kruskal

首先，kruskal求最小生成树不会的戳这里

求次小生成树倍增 LCA

关键在于次小生成树怎么求：

问自己一些问题

怎么求不严格次小生成树

不严格次小生成树为什么不严格

方法每次选择U—V之间的边，前提是最小生成树上不存在的边，添边之后删去较短边，使用LCA找到祖先，删边，这里保证次小生成树的是？只要添得边不是U-V在树上最小距离即可。

模板

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
typedef long long ll;
using namespace std;
const int M=1e5+100;
ll n,m,res,ans=0x3f3f3f3f,mx;
int f[M],fa[25][M],dep[M];
ll d[2][25][M];
bool used[3*M],vis[M];
vector<int> a[M];
struct Edge{
    int from, to;
    ll val;
    bool operator < (const Edge y){
        return val < y.val;
    }
}e[3*M];
int F(int x){
    if(f[x]==x) return x;
    return f[x]=F(f[x]);
}
void kruskal(){ //kruskal 算最大生成树（已保证任意两点之间最小限重最优）
    sort(e,e+m); int lef=n-1;
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=0;i<m && lef;++i){
        int x=F(e[i].from),y=F(e[i].to);
        if(x!=y){
            f[x]=y; res+=e[i].val;
            used[i]=1; --lef;
            mx=max(mx , e[i].val);
        }  
    }
}
void dfs(int x){    //深搜建树（可能不止一棵，因为数据未保证是连通图） 
    vis[x]=true;
    for(int i=1;i<=23;++i){
        fa[i][x]=fa[i-1][fa[i-1][x]];
        ll t1=d[0][i-1][x], t2=d[0][i-1][fa[i-1][x]];
        d[0][i][x]=max(t1 , t2);
        d[1][i][x]=max(d[1][i-1][x] , d[1][i-1][fa[i-1][x]]);
        if(t1!=t2) d[1][i][x]=max(d[1][i][x] , min(t1 , t2));
    }
    for(int i=0;i<a[x].size();++i){
        int t=e[a[x][i]].to+e[a[x][i]].from-x;
        if(vis[t]) continue;    //vis为1表示是父节点 
        dep[t]=dep[x]+1; fa[0][t]=x;
        d[0][0][t]=e[a[x][i]].val; dfs(t);
    }
}
int lca(int u,int v){
    if(dep[u]<dep[v])
        swap(u,v);
    if(dep[u]!=dep[v]){     //将深度做相等
        for(int i=23,h=dep[u]-dep[v];i>=0;--i)
        if(h&(1<<i)) u=fa[i][u];
    }
    if(u==v) return u;  //如果已经在一个节点上就直接返回 
    for(int i=23;i>=0;--i) if(fa[i][u]!=fa[i][v])
        u=fa[i][u] , v=fa[i][v];
    return fa[0][u];
}
ll get(int u,int v,int c){
    int fht=lca(u,v);
    ll m1=0,m2=0;
    for(int i=23,h1=dep[u]-dep[fht],h2=dep[v]-dep[fht];i>=0;--i){
        if(h1&(1<<i)){
            if(d[0][i][u]>m1) m2=m1,m1=d[0][i][u];
            else if(d[0][i][u]>m2) m2=d[0][i][u];
            else m2=max(m2 , d[1][i][u]);
        } if(h2&(1<<i)){
            if(d[0][i][v]>m1) m2=m1,m1=d[0][i][v];
            else if(d[0][i][v]>m2) m2=d[0][i][v];
            else m2=max(m2 , d[1][i][v]);
        }
    } if(m1==c) return c-m2;
    else return c-m1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i){
        int u,v; ll w;
        scanf("%d%d%lld",&u,&v,&w);
        e[i].from=u;
        e[i].to=v;
        e[i].val=w;
    } kruskal();
    for(int i=0;i<m;++i) if(used[i]){
        a[e[i].from].push_back(i);
        a[e[i].to].push_back(i);
    } dep[1]=1; dfs(1);
    for(int i=0;i<m;++i) if(!used[i]){
        if(e[i].val-mx>ans) break;
        ll t=get(e[i].from , e[i].to , e[i].val);
        ans=min(ans , t);
    } return printf("%lld\n",res+ans),0;

相关文章