AC

♻️lzhh_lzhh32  •  3个月前


#include<bits/stdc++.h>
using namespace std;
int n,m,w;
struct road{
	int a,b;
	int len;
}d[1000];
bool cmp(road x,road y){
	return x.len<y.len;
}
int group[105];
int find(int x){
	if(x!=group[x]){
		group[x]=find(group[x]);
	}
	return group[x];
}

int main(){
	cin>>n>>m;	//n点m边
	for(int i=0;i<m;i++){
		cin>>d[i].a>>d[i].b>>d[i].len;	
	}
	cin>>w;
	sort(d,d+m,cmp);
	for(int i=1;i<=n;i++){
		group[i]=i;
	}
	long long ans=0; 
	for(int i=0;i<m;i++){
		if(find(d[i].a)!=find(d[i].b)){		//不在同一个连通分量 
			ans+=d[i].len;
			group[find(d[i].a)]=find(d[i].b);
		}
	}
	cout<<ans<<' '<<ans*w<<endl;
	return 0; 
}

评论:

请先登录,才能进行评论