[数据结构与算法]Kruskal算法

Kruskal算法

学到了Kruskal的妙用，而且，能用prim的一定能用Kruskal算法，能用Kruskal算法的prim不一定好搞

局域网

这个题目中可是没有保证图一定联通，所以选点就比较难写，也就是Prim算法难搞，那就用Kruskal算法呗，大意为给你一个图，让你去掉权值和尽可能大的边，还要保证图联通

然后就转化成，每个连通块求一个一个最小生成树，就直接kruskal，仔细一想，确实，毕竟Kruskal算法不受连通图影响haha

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m;
struct node
{
    int a, b, c;
    bool operator< (const node &t)const
    {
        return c < t.c;
    }
}r[210];

int p[110];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 1; i <= m; i ++ )
    {
        cin >> r[i].a >> r[i].b >> r[i].c;
        
    }
    
    sort (r+1, r+1+m);
    int res = 0;
    int a, b, w;
    for(int i=1; i<=m; i++)
    {
        a=r[i].a;
        b=r[i].b;
        w=r[i].c;
        
        a=find(a); b = find(b);
        
        if(a != b)
        {
            p[a] = b;
        }
        else res += w;
    }
    
    cout << res << '\n';
    return 0;
}