最小生成树
（1）n小(点少)
    prim算法
（2）n大(点多)
    kruskal算法

858. Prim算法求最小生成树

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=510;
int n,m,dist[N],g[N][N];//dist[i]表示的i到集合的距离 
bool st[N];
/*
    prim算法（无向图）：
    (1)需要三个东西：初始化的邻接矩阵，初始化的dist数组，和状态st数组 
    (2)第一层循环n次，然后假设还不存在集合外的点mark=-1 
       第二层循环，找到集合外离集合最近的点，标记这个点，并改变这个点的状态 
       如果这次不是第一次去找集合外的点，并且这个mark点到集合的距离无穷远，
       那么说明这个图的连通块不止一个，也就是说不存在最小生成树
       再如果，这次不是第一次去找集合外的点，那么就加上这个点到集合的距离
       最后一次循环,用mark这个点去更新每个点到集合的距离 

    prim与Dijkstra的区别：
    (1)prim的dist表示到集合的距离,Dijkstra的dist表示到源点的距离
    (2)prim的st表示的是在集合里面,Dijkstra的st表示这个点是已经确定最短距离
    (3)prim需要对第一次循环做一些判断，也就是判断此时是不是空集合
    (4)更新距离的方程不一样， 
       Dijkstra: dist[j]=min(dist[j],dist[mark]+g[mark][j])
       prim:     dist[j]=min(dist[j],g[mark][j]) 
*/
int prim()
{
    int re=0;//最小生成树的总路径长度 
    memset(dist,0x3f3f3f3f,sizeof dist);
    for(int i=0;i<n;i++)
    {
        int mark=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(mark==-1||dist[mark]>dist[j]))
                mark=j;
        }
        st[mark]=true;
        if(i!=0&&dist[mark]==0x3f3f3f3f)
            return 0x3f3f3f3f;
        if(i!=0)
            re+=dist[mark];
        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],g[mark][j]);
        }
    }
    return re;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(g,0x3f3f3f3f,sizeof g);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(c,g[b][a]);//无向图 
    }
    int t=prim();
    if(t==0x3f3f3f3f)
        puts("impossible");
    else
        printf("%d\n",t);
    return 0;
}

859. Kruskal算法求最小生成树

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,cnt,re;//cnt记下生成树的边数
int p[N]; 
/*
    kruskal算法：
    (1)用结构体存储每一条边
    (2)按照边的权重升序排列
    (3)枚举每一条边，如果这个边的两端有着同一个祖先，则说明它俩在一个连通块中
       如果不在，则在a的祖先中加入n这个子女
       增加生成树的边数以及它的总路径 
*/
struct Edge
{
    int a,b,w;
    bool operator< (const Edge &e)const
    {
        return w<e.w;
    }
    //这个的意思是重载小于符号，就是在sort的时候，排序按这个规则排序
    //当来了一个结构体e,这个结构体就按升序排序 
}edges[N];
int find(int x)//并查集模板：找到x这个数的祖先，通过递归p[x]代替x去找祖先，也就是一个找一个 
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}
int kruskal()
{
    for(int i=1;i<=n;i++)
        p[i]=i;
    sort(edges,edges+m);//将每一条边按照权重升序排好 
    for(int i=0;i<m;i++)//枚举每一条边 
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a);b=find(b);//找到a,b的祖宗 
        if(a!=b)//判断a,b是不是同一个祖先， 如果不是，那么在a这个祖先的子女中加入b 
        {
            p[a]=b;
            re+=w;
            cnt++;//增加生成树的边数 
        }
    }
    if(cnt<n-1)//如果"生成树"的边数小于n-1,说明不存在生成树 
        return 0x3f3f3f3f;
    else
        return re;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edges[i]={a,b,c};
    }
    if(kruskal()==0x3f3f3f3f)
        puts("impossible");
    else
        printf("%d\n",re);
    return 0;
}