社区讨论

蒟蒻又求助,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 条回复,欢迎继续交流。

正在加载回复...