chenzhiyuan0923 @ 2022-10-16 20:22:48
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int maxv=2e5+10;
long long n,m,f[maxv];
long long ans;
struct edge{
int u,v,w;
};
edge g[maxn];
bool cmp(edge a,edge b){
return a.w<b.w;
}
int find(int a){
if(f[a]==a) return a;
f[a]=find(f[a]);
return f[a];
}
void kruskal(){
int cnt=0;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++) {
int x=g[i].u,y=g[i].v;
int fx=find(x);
int fy=find(y);
if(fy!=fx){
f[fx]=fy;
ans+=g[i].w;
cnt++;
}
if(cnt==n-1) break;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w);
sort(g+1,g+1+m,cmp);
kruskal();
cout<<ans;
}
by ImposterAnYu @ 2022-10-16 20:25:24
@xchenzhiyuan 是不是就是,如果所有的
by ImposterAnYu @ 2022-10-16 20:26:08
@owo_ImposterAnYu_owo 打错了,是
如果所有的
m 条边都判完之后还没能挑出n - 1 条边,就代表图不连通
by Im3tsmh @ 2022-10-16 20:30:32
@Yanyu_Kruay 你这个只能判定
by Im3tsmh @ 2022-10-16 20:31:46
在每次连边的时候记录
by Yiowerr @ 2022-10-16 20:33:35
@TryToThink 当时写的时候没注意dbq ww
by chenzhiyuan0923 @ 2022-10-16 20:56:38
@owo_ImposterAnYu_owo 感谢,已A
by chenzhiyuan0923 @ 2022-10-16 20:57:05
@TryToThink 感谢