胖达和阿极 @ 2022-07-26 23:00:19
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int n,m,fa[N];
struct edge{
int u,v,w;
bool operator <(const edge &a1) const{
return w<a1.w;
}
}a[N];
int find(int x){
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
bool cmp(edge a1,edge a2){
return a1.w<a2.w;
}
long long kruskal()
{
long long cnt = 0,sum =0;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++){
if(find(a[i].u)!=find(a[i].v)){
fa[a[i].v] = fa[a[i].u];
sum += a[i].w;
cnt++;
if(cnt == n-1){
return sum;
}
}
}
return -1;
}
int main(){
cin>>n>>m;
int g1,g2,g3;
for(int i=1;i<=n;i++){
fa[i] = i;
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&g1,&g2,&g3);
a[i].u=g1;a[i].w=g3;a[i].v=g2;
}
int k1 = kruskal();
if(k1==-1){
cout<<"orz";
}else{
cout<<k1;
}
return 0;
}
by Benny_Li @ 2022-10-05 20:33:45
另外这种涉及图论的题目竟然只有