局域网-题解

查看题目戳这里

一道最小生成树的裸题，这里我们用kruskal来做

kruskal 是一种求最小生成树的算法，时间复杂度为O(nlogn)

它的算法思路是这样的：

我们根据边的权值将所有边排序，然后枚举每条边，用并查集去查询这条边的两个端点是否在同一集合内，若在同一集合内，则删掉这条边，若不在同一结合则加入这条边，并将这两个端点所在的集合合并。
附一下代码：

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

using namespace std;

int n,m,q[6000];

struct lalala{
    int x,y,z,save;
}a[210000];

int mysort(lalala a,lalala b)
{
    return a.z < b.z;
}

int work(int x,int y)
{
    while(q[q[x]] != q[x]) q[x] = q[q[x]];
    while(q[q[y]] != q[y]) q[y] = q[q[y]];
    if(q[x] == q[y]) return 1;
    else
    {
        q[q[y]] = q[x];
        return 0;
    }
}

int main()
{
    long long ans = 0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) q[i]=i;
    for(int i=1; i<=m; i++) 
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
        ans += a[i].z;
    }
    sort(a+1,a+m+1,mysort);
    for(int i=1;i<=m;i++)
    {
        if(!work(a[i].x,a[i].y)) ans -= a[i].z;
    }
    cout << ans;
    return 0;
}