最小生成树

何为最小生成树？

最小生成树就是对于一个连通图，保留若干条边，使图依然联通，且边权和最小。

因为\(n\)个点的连通图（以下自动默认为连通图，），最少要有\(n-1\)条边。所以对于一个图的最小生成树，也一定只有\(n-1\)条边。反证一下（此证明仅限于非负边权）：如果这个图的最小生成树不止有\(n-1\)条边，因为只需保留\(n-1\)条边即可保持联通，所以我们一定可以找到一条边，将其删去，仍保持图联通。这样的话就与我们的定义不符了。当然，对于存在负边权的情况，显然是不能这么简单证明的，所以我们这里只讨论正边权。

\(Kruskal\)

由于最小生成树的上述特性，\(Kruskal\)算法便应运而生了。

简单的叙述就是：先把\(n\)个点分布在\(n\)个集合中，将\(m\)条边从小到大排序，依次遍历。如果当前边所连接的两个点不在同一集合，则加上这条边，然后合并两个集合；如果在同一集合则忽略。直到选择了\(n-1\)条边后，最小生成树也就求出来了。这里比较显然，就不证明了。

题目链接

下面放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
#define maxn 5005
#define maxm 200005
using namespace std;

inline ll read(){
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}int n,m,sum,ans;

struct ahaha{
    int u,v,w;
    inline bool friend operator<(const ahaha x,const ahaha y){
        return x.w<y.w;
    }
}e[maxm];

int f[maxn];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    f[fx]=fy;
}

int main(){
    n=read();m=read();
    for(int i=1;i<=m;++i)
        e[i]={read(),read(),read()};
    for(int i=1;i<=n;++i)f[i]=i;
    sort(e+1,e+m+1);
    for(int i=1;i<=m;++i){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(find(u)==find(v))continue;
        merge(u,v);++sum,ans+=w;
        if(sum==n-1)break;
    }
    if(sum<n-1)puts("orz");
    else printf("%d\n",ans);
    return 0;
}

\(Prim\)

除了\(Kruskal\)以外，还有一种算法叫做\(Prim\)算法。\(Prim\)算法简单来说就是：先把一个点放到集合\(B\)里，然后把剩下的点放到集合\(A\)里，每次把从集合\(A\)连向集合\(B\)的最短边拿出来，然后把最短边所连接的集合\(A\)中的点移动到集合\(B\)中，直到所有点都放到了集合\(B\)中，最小生成树也就求好了。

由于我几乎没有用过这种算法，这里也就不放代码了。

\(Kruskal\)在稀疏图中的复杂度更优秀，而\(Prim\)在稠密图中要更胜一筹，具体采用哪种方法，还要看大家的喜好还有题目要求。

至于题目推荐，这种类型的题太多了，我就不推荐了

如果这篇博客对你有些许帮助的话，不妨点推荐再走吧