最小生成树

Kruskal 最小生成树

namespace Kruskal
{
    using piii=pair<pair<int,int>,int>;
    vector<piii> E;
    int cnt,sum;

    namespace DSU
    {
        int N;
        int fa[MAX],siz[MAX];
        inline void init() {for(int i=1;i<=N;++i) fa[i]=i,siz[i]=1;}
        int find(int x) {if(fa[x]==x) return x; return fa[x]=find(fa[x]);}
        inline void merge(int x,int y) {x=find(x),y=find(y); if(siz[x]<siz[y]) Swp(x,y); siz[x]+=siz[y],fa[y]=x;}
        inline bool check(int x,int y) {return find(x)==find(y);}
    }
    using namespace DSU;

    inline void solve()
    {
        N=n,init();
        sort(E.begin(),E.end(),[&](piii a,piii b){return a.se<b.se;});
        for(auto [point,val]:E)
        {
            int x=point.fi,y=point.se;
            if(check(x,y)) continue;
            merge(x,y),sum+=val;
            if(++cnt==n-1) break;
        }
    }
}

Prim 最小生成树

namespace Prim
{
    vector<pii> G[MAX];
    int dis[MAX],vis[MAX],now=1;
    int sum,tot;

    inline void solve()
    {
        for(int i=2;i<=n;++i) dis[i]=INF;
        for(auto [to,val]:G[1]) cmin(dis[to],val);
        while(++tot<n)
        {
            int mix=INF;
            vis[now]=1;
            for(int i=1;i<=n;++i) if(!vis[i]&&dis[i]<mix) mix=dis[i],now=i;
            sum+=mix;
            for(auto [to,val]:G[now]) if(dis[to]>val&&!vis[to]) dis[to]=val;
        }
    }
}

Boruvka 最小生成树

namespace Boruvka
{
    using piii=pair<pair<int,int>,int>;
    vector<piii> E;
    int cnt,sum,flag;
    int best[MAX],used[MAX*40];

    namespace DSU
    {
        int N;
        int fa[MAX],siz[MAX];
        inline void init() {for(int i=1;i<=N;++i) fa[i]=i,siz[i]=1;}
        int find(int x) {if(fa[x]==x) return x; return fa[x]=find(fa[x]);}
        inline void merge(int x,int y) {x=find(x),y=find(y); if(siz[x]<siz[y]) Swp(x,y); siz[x]+=siz[y],fa[y]=x;}
    }
    using namespace DSU;

    inline void solve()
    {
        auto better=[&](int a,int b)->bool
        {
            if(!(~b)) return 1;
            if(E[a].se!=E[b].se) return E[a].se<E[b].se;
            return a<b;
        };

        N=n,init();
        do
        {
            flag=0,memset(best,-1,sizeof best);
            for(int i=0;i<((int)E.size());++i)
            {
                int x=E[i].fi.fi,y=E[i].fi.se;
                x=find(x),y=find(y);
                if(x==y||used[i]) continue;
                if(better(i,best[x])) best[x]=i;
                if(better(i,best[y])) best[y]=i;
            }
            for(int i=1,id=best[i];i<=n;++i,id=best[i]) if(~id&&!used[id]) flag=1,++cnt,sum+=E[id].se,merge(E[id].fi.fi,E[id].fi.se),used[id]=1;
        }while(flag);
    }
}
using namespace Boruvka;

Kruskal 重构树

namespace KruskalTree
{
    using piii=pair<pair<int,int>,int>;
    vector<piii> E;
    vector<int> G[MAX];
    int cnt,val[MAX];

    namespace DSU
    {
        int N;
        int fa[MAX],siz[MAX];
        inline void init() {for(int i=1;i<=N;++i) fa[i]=i,siz[i]=1;}
        int find(int x) {if(fa[x]==x) return x; return fa[x]=find(fa[x]);}
        inline void merge(int x,int y) {x=find(x),y=find(y); if(siz[x]<siz[y]) Swp(x,y); siz[x]+=siz[y],fa[y]=x;}
        inline bool check(int x,int y) {return find(x)==find(y);}
    }
    using namespace DSU;

    inline void solve()
    {
        N=n,init();
        sort(E.begin(),E.end(),[&](piii a,piii b){return a.se<b.se;});
        for(auto [point,Eval]:E)
        {
            int x=point.fi,y=point.se;
            if(check(x,y)) continue;
            ++cnt,merge(x,y),val[cnt+n]=Eval;
            G[cnt+n].eb(x),G[x].eb(cnt+n),G[cnt+n].eb(y),G[y].eb(cnt+n);
            if(cnt==n-1) break;
        }
    }
}