1 条题解

  • 1
    @ 2024-2-21 17:04:04
    #include<cstdio>
    #include<algorithm> 
    
    using namespace std;
    
    #define int long long 
    
    int n,m,fa[300005],ans;
    struct node{
    	int x,y,z;
    }h[300005];
    
    bool operator < (node x,node y){
    	return x.z<y.z;
    }
    
    int get(int x){
    	if(x==fa[x])return x;
    	return fa[x]=get(fa[x]);
    }
    
    void Kruskal(){
    	sort(h+1,h+m+1);
    	for(int i=1;i<=n;i++)fa[i]=i;
    	for(int i=1;i<=m;i++){
    		int x=get(h[i].x),y=get(h[i].y);
    		if(x==y)continue;
    		fa[x]=y;
    		ans+=h[i].z;
    	}
    } 
    
    signed main(){
    	scanf("%lld %lld",&n,&m);
    	for(int i=1;i<=m;i++)
    		scanf("%lld %lld %lld",&h[i].x,&h[i].y,&h[i].z);
    	Kruskal();
    	printf("%lld",ans);
    	return 0;
    }
    
    • 1

    信息

    ID
    3
    时间
    1000ms
    内存
    512MiB
    难度
    9
    标签
    (无)
    递交数
    7
    已通过
    7
    上传者