最小生成树

一月 23, 2022

MST

设$N=(V,E)$是一个连通网，$U$是顶点集$V$的一个非空子集，边$(u,v)$是一个具有最小权值的边，其中$u\in U,v\in V-U$则必存在一棵包含边$(u,v)$的最小生成树

Prim

思路

将所有的点分为两个点集，一个是已经生成的最小生成树的点集，另外一个是已经在已生成的树里面的点，另一个是还没有生成的树中的点的集合
开始时先随机选择一个点到第一个集合中
每一次选择一条边，这条边的两个顶点分别属于两个集合当中且权值最小，将这条边和点加入到选中的集合中
选择$N-1$条边生成最小生成树

代码

P3366 【模板】最小生成树 - 洛谷

上面这道题作为例题了

#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<bitset>
#include<set>
#include<cmath>
using namespace std;

#define rint register int
#define Int64 long long
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define clr(x,y) memset(x,y,sizeof(x))
#define sqar(x) (x)*(x)
#define lowbit(x) (x&(-x))
#define swp(x,y) x^=y,y^=x,x^=y
#define Maxn 5005
#define Maxm 200005
#define inf 0x3f3f3f3f

int dist[Maxn];
struct edge{
    int to;
    int val;
};
vector<edge>G[Maxn];
bool vis[Maxn];

int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
        int u,v,z;scanf("%d%d%d",&u,&v,&z);
        G[u].push_back({v,z});
        G[v].push_back({u,z});
    }
    for(int i=1;i<=N;i++)dist[i]=inf;clr(vis,0);
    dist[1]=0;vis[1]=1;
    vector<edge>::iterator iter=G[1].begin();
    while(iter!=G[1].end()){
        edge p=*iter;
        int v=p.to;
        dist[v]=min(dist[v],p.val);//注意重边
        iter++;
    }
    int ans=0;
    for(int i=1;i<=N-1;i++){
        int pos;
        int minc=inf;
        for(int j=1;j<=N;j++){
            if(minc>dist[j] && vis[j]==0){
                minc=dist[j];
                pos=j;
            }
        }
        ans+=minc;
        vis[pos]=1;
        iter=G[pos].begin();
        while(iter!=G[pos].end()){
            edge p=*iter;
            if(dist[p.to]>p.val&&vis[p.to]==0)dist[p.to]=p.val;
            iter++;
        }
    }
    bool tag=0;
    for(int i=1;i<=N;i++){
        if(vis[i]==0){tag=1;break;}
    }
    if(tag)printf("orz");
    else cout<<ans;
    return 0;
}

Kruscal

别的不说，我觉得这个算法简直是永远的神，简单易懂好写

思路

把每一条边按照权值的大小进行排序，令最小生成树初始状态为$N$个点，没有边的非联通图
从最小的边开始，假如边的两个点不在同一个连通分量，就选择这条边(通过并查集来进行判断)
选择$N-1$条边后最小生成树生成，或者选完了过后还没$N-1$条被选说明选不出来

代码

#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<bitset>
#include<set>
#include<cmath>
using namespace std;

#define rint register int
#define Int64 long long
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define clr(x,y) memset(x,y,sizeof(x))
#define sqar(x) (x)*(x)
#define lowbit(x) (x&(-x))
#define swp(x,y) x^=y,y^=x,x^=y
#define Maxn 5005
#define Maxm 200005

class DSU{
private:
    int belong[Maxn];
public:
    void init(){for(int i=0;i<Maxn;i++)belong[i]=i;}
    int find(int u){
        if(u==belong[u])return u;
        return belong[u]=find(belong[u]); 
    }
    bool islink(int u,int v){
        int fu=find(u);
        int fv=find(v);
        return fu==fv;
    }
    void link(int u,int v){
        int fu=find(u);
        int fv=find(v);
        belong[fu]=fv;
    }
}D;

struct edge{
    int u;
    int v;
    int val;

    bool operator <(const edge& cmp)const{
        return val<cmp.val; 
    }
}E[Maxm];

int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    D.init();
    int N,M;scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
        int u,v,z;scanf("%d%d%d",&u,&v,&z);
        E[i]={u,v,z};
    }
    sort(E+1,E+1+M);
    int tot=0,now=1,ans=0;
    while(now<=M){
        int u=E[now].u;
        int v=E[now].v;
        if(D.islink(u,v)==false){
            D.link(u,v);
            tot++;
            ans+=E[now].val;
        }
        if(tot==N-1)break;
        now++;
    }
    if(tot!=N-1)printf("orz");
    else printf("%d",ans);
    return 0;

    
}

查看评论

1. MST
2. Prim