社区讨论
蒟蒻又求助,Kruskal模板写挂了
学术版参与者 5已保存回复 22
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 22 条
- 当前快照
- 1 份
- 快照标识符
- @mi7ctkng
- 此快照首次捕获于
- 2025/11/20 19:34 4 个月前
- 此快照最后确认于
- 2025/11/20 22:38 4 个月前
听取WA声一片,输出全是0
CPP#include<cstdio>
#include<algorithm>
using namespace std;
int f[5005];
int n,m;
inline void MakeSet(int n){ //并查集初始化
for(register int i=1;i<=n;i++) f[i]=i;
}
inline int find(int k){ //并查集查询
if(f[k]==k) return k;
else return f[k]=find(f[k]);
}
#define unite(x,y) f[find(x)]=find(y); //并查集合并,define纯属脑子一热
struct edge{ //无向存边
int u,v,w;
}Edge[200005];
bool cmp(edge a,edge b){ //比较边大小
return a.w<b.w;
}
inline void Kruskal(){
sort(Edge,Edge+m,cmp);
long long ans=0; int cnt=0; //cnt是边数
for(register int i=0;i<m;i++){
if(find(Edge[i].u)==find(Edge[i].v)) continue;
ans+=Edge[i].w;
unite(Edge[i].u,Edge[i].v);
if(++cnt==n-1) break;
}
printf("%d",ans);
return;
}
inline int read(){ //快读,总不能这里出锅吧?
static int x;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x>>3)+ch-'0';
ch=getchar();
}
return x;
}
int main(void){
n=read(); m=read();
for(register int i=0;i<m;i++){
Edge[i].u=read(); Edge[i].v=read(); Edge[i].w=read();
}
Kruskal();
return 0;
}
回复
共 22 条回复,欢迎继续交流。
正在加载回复...