kruskal44pt求调,玄关
查看原帖
kruskal44pt求调,玄关
880874
Hu_cosine楼主2023/10/20 21:31

扫复赛知识点时突然不会打了

失分代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m,f[5005],ans;
bool ctld=0;
struct node{
	int x,y,w;
}t[200005];
bool cmp(node a,node b){
	return a.w<b.w;
}
int find(int x){
	if(x!=f[x])x=f[x]=f[f[x]];
	return x;
}
void kruskal(){
	int cnt=0;
	sort(t+1,t+m+1,cmp);
	for(int i=1;i<=m;i++){
		int xx=find(t[i].x),yy=find(t[i].y);
		if(xx==yy)continue;
		ans+=t[i].w;
		f[xx]=yy;
		if(++cnt==n-1)break;
	}
	if(cnt!=n-1)ctld=1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)f[i]=i;
	for(int i=1;i<=m;i++)scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].w);
	kruskal();
	if(!ctld)printf("%d\n",ans);
	else printf("orz\n");
	return 0;
}
2023/10/20 21:31
加载中...