最小生成树

luckydrawbox · 2022-09-12 11:31:20 · 个人记录

Kruskal

需要并查集和建边中的高级版本。

变量

函数

代码

struct Kruskal{
    Graph<N,N<<1> Kru;
    pair<int,pair<int,int> >a[M];
    int m;
    bool ask(int n){
        m=Kru.tot=0;
        int cnt=0;
        mfs.init(n);
        for(int i=1;i<=n;i++){
            for(int j=G.head[i];j;j=G.nxt[j]){
                int y=G.ver[j];
                int z=G.edge[j];
                if(i<y)
                    a[++m]=(make_pair(z,make_pair(i,y)));
            }
        }
        sort(a+1,a+m+1);
        for(int i=1;i<=m;i++){
            int u=a[i].second.first;
            int v=a[i].second.second;
            int w=a[i].first;
            if(mfs.get(u)!=mfs.get(v)){
                mfs.merge(u,v);
                cnt++;
                Kru.add(u,v,w);
                Kru.add(v,u,w);
            }
            if(cnt==n-1)
                return 1;
        }
        return 0;
    }
}tu;

Prim

宏定义

变量

函数

代码

#define PT int
PT a[N][N];
struct Prim{
    PT d[N];
    bool v[N];
    PT ask(int n){
        memset(d,0x3f,sizeof(d));
        memset(v,0,sizeof(v));
        d[1]=0;
        PT ans=0;
        for(int i=1,x;i<n;i++){
            x=0;
            for(int j=1;j<=n;j++)
                if(!v[j]&&(!x||d[j]<d[x]))
                    x=j;
            v[x]=1;
            for(int j=1;j<=n;j++)
                if(!v[j])
                    d[j]=min(d[j],a[x][j]);
        }
        for(int i=2;i<=n;i++)
            ans+=d[i];
        return ans;
    }
}tu;