Java 解法, 执行用时: 1567ms, 内存消耗: 33624K, 提交时间: 2023-08-13 14:02:04

import java.util.*;
import java.io.*;
public class Main {
	static int[] p=new int[100010];
	public static void main(String[] args) throws NumberFormatException, IOException {
        Read sc=new Read();
        int n=sc.nextInt();
        int m=sc.nextInt();
        Edge[] edges=new Edge[m];
        for(int i=1;i<=n;i++)p[i]=i;
        for(int i=0;i<m;i++) {
        	edges[i]=new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(edges,new Comparator<Edge>() {
        	public int compare(Edge e1,Edge e2) {
        		return e1.c-e2.c;
        	}
		});
        
        long res=0;
        for(int i=0;i<m;i++) {
        	int a=edges[i].a;
        	int b=edges[i].b;
        	if(find(a)!=find(b)) {
        		res+=edges[i].c;
        		p[find(a)]=find(b);
        	}
        }
        System.out.println(res);
	}
	static int find(int x) {
		if(x!=p[x])p[x]=find(p[x]);
		return p[x];
	}
}
class Edge{
	int a,b,c;
	public Edge(int a,int b,int c) {
		this.a=a;
		this.b=b;
		this.c=c;
	}
	
}
class Read{
	StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	int nextInt() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
	String next() throws IOException {
		st.nextToken();
		return st.sval;
	}
}

C++ 解法, 执行用时: 250ms, 内存消耗: 6612K, 提交时间: 2023-08-13 14:01:34

#include<bits/stdc++.h>
using namespace std;

struct h
{
	int x,y,w;
}E[500005];
int i,S=0,n,m,V[100005];
int F(int x)
{
	if(V[x]!=x)return V[x]=F(V[x]);
	return x;
}
void U(int x,int y)
{
	int a=F(x),b=F(y);
	if(a!=b)V[a]=b;
}
bool cmp(h a,h b)
{
	return a.w<b.w;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=0;i<m;i++)scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].w);
	sort(E,E+m,cmp);
	for(i=1;i<=n;i++)V[i]=i;
	for(i=0;i<m;i++)
		if(F(E[i].x)!=F(E[i].y))U(E[i].x,E[i].y),S+=E[i].w;
	printf("%d\n",S);
}