♻️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;
}
评论:
请先登录,才能进行评论