莫欺少年穷，修魔之旅在这开始—>算法提高课题解

注意：

题目是让我们求一棵最小“生成森林”，即要求每棵生成树都是最小的

可参考： Kruskal算法求最小生成树

#include<bits/stdc++.h>

using namespace std;

const int N = 110, M = 210;

int n,m;
struct Edge
{
    int a,b,w;
    bool operator< (const Edge &t) const 
    {
        return w<t.w;
    }
}e[M];
int p[N];

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=0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        e[i]={a,b,w};
    }

    sort(e,e+m);

    int res=0;
    for(int i=0;i<m;i++)
    {
        int a=find(e[i].a),b=find(e[i].b),w=e[i].w;

        //不在同一个集合
        if(a!=b) p[a]=b;

        //在同一个集合
        else res+=w;
    }

    cout<<res<<endl;

    return 0;
}