社区讨论

kruskal44pt求调,玄关

P3366【模板】最小生成树参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo0zu1jh
此快照首次捕获于
2023/10/22 12:53
2 年前
此快照最后确认于
2023/10/22 12:53
2 年前
查看原帖
扫复赛知识点时突然不会打了
失分代码如下:
CPP
#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;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...