最小生成树算法模板
包含Kruskal和prim模板

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define maxn 2999
//kruskal 算法 贪心的求出最小生成树
struct node
{
    int u,v,w;
};//为了方便排序，建立一个结构体来存储边的关系
node e[maxn];
int n,m,sum=0,num=0,f[maxn+3];//f[]为并查集数组
//快排原函数
void quicksort(int left,int right)
{
    int i,j;
    if(left>right)
    return;
    i = left;
    j = right;
    while(i!=j)
    {
        while(e[j].w>=e[left].w&&i<j)
        {
        j--;
        }//先从右边找到一个比基准数小的
        while(e[i].w<+e[left].w&&i<j)
        {
            i++;
        }
        if(i<j)
        {
            swap(e[i],e[j]);
        }
    }
    swap(e[i],e[left]);
    quicksort(left,i-1);
    quicksort(i+1,right);
    return ;
}
int getf(int t)//递归找爹函数
{
    if(f[t]==t)
    return t;
    else
    {
        f[t] = getf(f[t]);//途中路径压缩
        return f[t];
    }
}
int amerge(int v,int u)//并查集合并子集函数，此处增加了判断两个点是否在同一个集合的功能
{
    int t1 = getf(v);
    int t2 = getf(u);
    if(t1!=t2)
    {
        f[t2] = t1;
        return 1;
    }
    return 0;
}
//在判断此边是否联通时，假如尚未联通则联通此边，直到满足cout == n-1即选用了N-1条边为止
//排序算法借鉴了贪心思想
int main()
{
int i;
while(~scanf("%d%d",&n,&m))
{
    for(i=1;i<=m;i++)//依次读入各边
    scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    quicksort(1,m);//按照边长（权值）依次排序
    for(i=1;i<=n;i++)
    {
    f[i] = i;
    }
    num = 0,sum = 0;
    //核心部分
    for(i=1;i<=m;i++)
    {
        if(amerge(e[i].u,e[i].v))//如果两个顶点尚未联通，则选用这条边
        {
            num++;
            sum+=e[i].w;
        }
        if(num==n-1)
        {
        break;
        }
    }
    printf("%d\n",sum);

}
return 0;
}

模板2：

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define inf 99999999
#define maxn 2002
//Prim算法模板
int e[maxn][maxn],book[maxn],dis[maxn],n,m,t1,t2,t3;
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                e[i][j]=0;
                else
                e[i][j]= inf;
            }
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&t1,&t2,&t3);
            e[t1][t2] = t3;
            e[t2][t1] = t3;
        }
        for(int i=1;i<=n;i++)
        {
            book[i] = 0;
            dis[i] = e[1][i];
        }
        int count = 0,sum = 0,min,j;
        book[1] = 1;//标记该点是否已经在生成树中
        count++;
        while(count<n)
        {
            min = inf;
            for(int i=1;i<=n;i++)
            {
                if(book[i]==0&&dis[i]<min)
                {
                    min = dis[i];
                    j = i;
                }
            }//从数组dis中找到离生成树最近的顶点，并加入生成树中
            book[j] = 1;
            count++;
            sum+=dis[j];//数组dis表示生成树到各个顶点的距离
            for(int k=1;k<=n;k++)//以J为中间点，更新生成树到每一个顶点的距离
            {
                if(book[k]==0&&dis[k]>e[j][k])
                dis[k] = e[j][k];//此处的松弛操作更改的是中间点到每个点（假如从该点到其他顶点更小的话则更新）
            }
        }
        //由于该算法是层层递推覆盖所以会取得最佳效果
        printf("%d\n",sum);
    }
    return 0;
}