zp20120123 @ 2024-07-27 13:30:38
附上错误代码
//kruskal
//最小生成树
//small
//sort
#include<bits/stdc++.h>
using namespace std;
int fa[5005];
struct node{
int u, v, w;
}a[200005];
bool cmp(node x, node y){
return x.w < y.w;
}
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y){
fa[find(x)] = find(y);
}
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main(){
int n = read(), m = read();
for(int i = 0; i < m; i++){
cin >> a[i].u >> a[i].v >> a[i].w;
}
sort(a, a + m, cmp);
for(int i = 0; i <n; i++){
fa[i] = i;
}
int tot = 0;
for(int i = 0; i < m; i++){
if(find(a[i].u) != find(a[i].v)){
merge(a[i].u, a[i].v);
tot += a[i].w;
}
}
cout << tot;
return 0;
}
我知道要输出
@Laugh_at_the_sky
by wa_wa_wa_wa @ 2024-07-27 13:48:41
@zp20120123 kruskal每加一条边就让 cnt++ 最后判断cnt是否等于n-1就可以了
by wa_wa_wa_wa @ 2024-07-27 13:56:18
求互关
by zp20120123 @ 2024-07-27 14:03:45
谢谢
by zp20120123 @ 2024-07-27 15:30:19
@wa_wa_wa_wa 我已过关,thank you!
by zhaoyonghao @ 2024-07-31 10:43:38
只要判断cnt==n-1就OK了
by zhaoyonghao @ 2024-07-31 10:44:34
我就这样写的