社区讨论
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 条回复,欢迎继续交流。
正在加载回复...