Hiscraft @ 2023-08-19 15:43:30
#include<bits/stdc++.h>
using namespace std;
struct node{
int u,v,l;
}a[114514];
int n,m,ans,f[11451];
bool cmp(node a,node b)
{
return a.l<b.l;
}
int q(int x){
if(f[x]==x) return x;
else return f[x]=q(f[x]);
}
//Kruskal 算法
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].l;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m&&n>1;i++){
if(q(a[i].u)==q(a[i].v)) continue;
f[q(a[i].u)]=q(a[i].v);
ans+=a[i].l;
}
if(ans) cout<<ans;
else cout<<"orz";
}
by ruojiyz @ 2023-08-19 15:59:00
@Hiscraft 帮你看了一下,问题有点多:
1.a数组开小了,导致RE,因为边有200000条你只开了100000左右。
2.kruskal是要选n - 1条边,你这里是忘写n--了吧。
3.并不是ans有值就输出,而是n == 1才输出ans,因为n == 1才能说明选出了n - 1条边即图联通,否则图是不连通的,ans有值只能说明你选过边。
代码自己调,加油吧。