#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
vector<int> p(3001),rnk(3001,1);
int find(int a){
return p[a]==a?a:p[a]=find(p[a]);
}
bool same(int a,int b){
return find(a)==find(b);
}
void merge(int a,int b){
/*if(!same(a,b))*/{
if(rnk[find(a)]>rnk[find(b)]){
// num[find(a)]+=num[find(b)];
p[find(b)]=find(a);
}
else {
// num[find(b)]+=num[find(a)];
p[find(a)]=find(b);
}
if(rnk[find(a)]==rnk[find(b)])
rnk[find(b)]++;
}
}
int main(){
int n,e;
cin>>n>>e;
for(int i=1;i<=n;i++)
p[i]=i;
vector<vector<int> > a;
for(int i=0;i<e;i++){
int x,y,w;
cin>>x>>y>>w;
a.push_back({w,x,y});
}
sort(a.begin(),a.end(),[](const vector<int> &l,const vector<int> &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0])
return l[1]+l[2]<r[1]+r[2];
return false;
});
int sum=0;
for(int i=0;i<e;i++)
if(!same(a[i][1],a[i][2])){
merge(a[i][1],a[i][2]);
sum+=a[i][0];
}
cout<<sum<<endl;
}
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
vector<int> p(3001),rnk(3001,1);
int find(int a){
return p[a]==a?a:p[a]=find(p[a]);
}
bool same(int a,int b){
return find(a)==find(b);
}
void merge(int a,int b){
/*if(!same(a,b))*/{
if(rnk[find(a)]>rnk[find(b)]){
// num[find(a)]+=num[find(b)];
p[find(b)]=find(a);
}
else {
// num[find(b)]+=num[find(a)];
p[find(a)]=find(b);
}
if(rnk[find(a)]==rnk[find(b)])
rnk[find(b)]++;
}
}
int main(){
int n,e;
cin>>n>>e;
for(int i=1;i<=n;i++)
p[i]=i;
vector<vector<int> > a;
for(int i=0;i<e;i++){
int x,y,w;
cin>>x>>y>>w;
a.push_back({w,x,y});
}
sort(a.begin(),a.end(),[](const vector<int> &l,const vector<int> &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0])
return l[1]+l[2]<r[1]+r[2];
return false;
});
int sum=0;
for(int i=0;i<e;i++)
if(!same(a[i][1],a[i][2])){
merge(a[i][1],a[i][2]);
sum+=a[i][0];
}
cout<<sum<<endl;
}
Comments
Post a Comment