lcc_cc @ 2022-08-31 22:14:00
#include<bits/stdc++.h>
using namespace std;
struct node{
int h,t,w;
}a[5005];
int fa[5005],cnt,n,ans,m;
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
bool cmp(node x,node y){
return x.w<y.w;
}
void inti(){
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) cin>>a[i].h>>a[i].t>>a[i].w;
return;
}
void dj(){
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++){
int x=a[i].h,y=a[i].t,z=a[i].w;
int fx=find(x),fy=find(y);
if(fx==fy) continue;
fa[fx]=fy;
ans+=z;
cnt++;
}
if(cnt==n-1) cout<<ans;
else cout<<"orz";
return;
}
int main(){
inti();
dj();
return 0;
}
by lcc_cc @ 2022-08-31 22:14:54
为什么这份代码会MLE?不应该RE吗?
by lcc_cc @ 2022-08-31 22:15:28
记录
by songtj @ 2022-09-20 17:40:59
@lcc_cc 您都开完隐了,发评测记录有意义吗?
by zsyzsy_2012 @ 2022-09-27 15:13:30
@lcc_cc 还有,您的并查集合并是不是有问题呀
不只是合并当前,应该把这个节点的“阵营”的父亲设为另一个吧
by lcc_cc @ 2022-09-29 23:24:52
@ZhaoShanYang 有没有一种可能,我用了路径压缩
by zsyzsy_2012 @ 2022-09-30 07:26:45
@lcc_cc 这个题不用压缩,普通Kruskal并查集完全可以A
by lcc_cc @ 2022-09-30 20:29:06
@ZhaoShanYang 为什么要和复杂度过不去,也就一行的事