最小生成树模板

洛谷P3366

//Kruskal 贪心思想，每次都从权值最小的边开始选，配合并查集得到最小生成树
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 200000+5;

struct Node
{
    int u,v,w;
};

Node node[maxn];

int n,m;
int fa[5005];
int ans,cnt;
int flag=0;

bool cmp(Node a,Node b)
{
    return a.w<b.w;
}

int find (int x)
{
    while(x!=fa[x])         //让x和x的父亲变成他的父亲的父亲
        x=fa[x]=fa[fa[x]];  //直到找到祖先才结束循环(x==fa[x])就意味着找到爹了
    return x;
}

void kruskal()
{
    sort(node,node+m,cmp);   //将全部边变从小到大排序
    int eu,ev;
    for(int i=0;i<m;i++) 
    {
        eu=find(node[i].u),ev=find(node[i].v);//找祖先，祖先相同说明已经连通，这条边没有用
        if(eu==ev) continue;  
        ans+=node[i].w;
        fa[ev]=eu; //将这两个点合并
        cnt++;     //将这条边选入，计数加一
        if(cnt==n-1) break; //当选入的边等于n-1时，就有了最小生成树
    }
    if(cnt>=n) flag=1;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        fa[i]=i;        //并查集初始化
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&node[i].u,&node[i].v,&node[i].w);
    }
    kruskal();
    if(flag) 
    printf("orz
");
    else
    printf("%d",ans);
    return 0;
}

//prim 贪心思想，每次都找离树最近的点
#include <cstdio>
#include <cstdlib>
#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 200000 + 5;
int book[5005];       //用于记录这个点有没有被访问过
int dis[5005];        //用于记录距离树的距离最短路程
int maps[5005][5005]; //用于记录所有边的关系

int n, m;
int sum=0;
int flag=0;

void prim()
{
    for (int i = 1; i <= n; i++)
        dis[i] = maps[1][i];
    //初始化距离数组，默认先把离1点最近的找出来放好,这里记录的是各个节点离树的最短距离
    book[1] = 1; //记录1已经被访问过了
    int min, minIndex;
    for (int i = 1; i <= n - 1; i++) //1已经访问过了，所以循环n-1次
    {
        min = inf; //对于最小值赋值，其实这里也应该对minIndex进行赋值，但是我们承认这个图一定有最小生成树而且不存在两条相同的边
        //寻找离树最近的点
        for (int j = 1; j <= n; j++)
        {
            if (book[j] == 0 && dis[j] < min)
            {
                min = dis[j];
                minIndex = j;
            }
        }
        if(min==inf)    //找不到连通的点，无法生成连通图
        {
            flag=1;
            break;
        }
        book[minIndex] = 1;  //记录这个点已经被访问过了
        sum += dis[minIndex];
        for (int j = 1; j <= n; j++)
        {    //如果这点没有被访问过，而且这个点到任意一点的距离比现在到树的距离近那么更新
            if (book[j] == 0 && maps[minIndex][j] < dis[j])
                dis[j] = maps[minIndex][j];
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    //初始化maps，除了自己到自己是0其他都是边界值
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (i != j)
                maps[i][j] = inf;
            else
                maps[i][j] = 0;
        }
    int u, v, w;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        maps[u][v] = maps[v][u] = min(w , maps[u][v]);
    }
    prim();
    if(flag) 
    printf("orz
");
    else    
    printf("%d
", sum);
    return 0;
}