题解 | #挖沟#

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2*500000+10;
const int maxnn = 100000+10;
struct sy{
    int to;
    int next;
    int w;
} edge[maxn];
int head[maxn];
struct Node{
    int number;
    int w;
    bool operator < (const Node &n) const {
        return w>n.w;
    }
};
priority_queue<Node> pq;
bool vis[maxnn];
int cnt = 0;
int n, m;

void add_edge(int x, int y, int w)
{
    edge[++cnt].next = head[x];
    edge[cnt].to = y;
    edge[cnt].w = w;
    head[x] = cnt;
}
//普利姆算法，利用贪心的原理求最小生成树
int prim()
{
    int ans = 0;
    pq.push({1, 0});
    while (pq.size())
    {
        Node node = pq.top();
        pq.pop();
        int number = node.number;
        int w = node.w;
        if (vis[number]) continue;
        ans += w;
        vis[number] = true;
        //遍历这个点的其他边，找出没有遍历过的加入
        for (int i=head[number];i;i = edge[i].next)
        {
            int next = edge[i].to;
//             cout<<next<<" "<<edge[i].w<<endl;
            if (vis[next]) continue;
            pq.push({next, edge[i].w});
        }
    }
    return ans;
}

int main()
{
    int x, y ,w;
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y>>w;
        add_edge(x, y, w);
        add_edge(y, x, w);
    }
    int ans = prim();
    cout<<ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2*500000+10;
struct Node{
    int x, y, w;
} node[maxn];

bool comp(Node n1, Node n2)
{
    return n1.w<n2.w;
}
int fa[100000+10];
int n, m;

int find(int x)
{
    return fa[x]==0?x:fa[x] = find(fa[x]);
}


int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        cin>>node[i].x>>node[i].y>>node[i].w;
    }
    sort(node+1, node+1+m, comp);
    int ans = 0;
    for (int i=1;i<=m;i++)
    {
        int x = node[i].x;
        int y = node[i].y;
        int rootx = find(x);
        int rooty = find(y);
        if (rootx==rooty) continue;
        ans += node[i].w;
        fa[rootx] = rooty;
    }
    cout<<ans<<endl;
    return 0;
}