社区讨论
kruskal全wa,求指正
P3366【模板】最小生成树参与者 6已保存回复 21
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 21 条
- 当前快照
- 1 份
- 快照标识符
- @mi6vvw94
- 此快照首次捕获于
- 2025/11/20 11:40 4 个月前
- 此快照最后确认于
- 2025/11/20 16:04 4 个月前
样例对的,下载的一个测试数据也是对的,想不明白问题出在哪
CPP#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 5010
#define maxm 200010
inline int read(){
int x = 0; char c = getchar();
while(c>'<'||c>'9') c=getchar();
while(c>='0'&&c<='9'){
x = (x<<3)+(x<<1)+(c-'0');
c = getchar();
}
return x;
}
int n,m;
struct edge{
int u,v,w;
bool operator< (const edge &a) const{
return w<a.w;
}
}e[maxm];
int cnt = 0;
inline void addedge(int u,int v,int w){e[++cnt].u = u; e[cnt].v = v; e[cnt].w = w;}
//___________并查集_____________________
struct bingchaji{
int fa[maxn],size[maxn];
void ini(){for(int i = 1; i <= n; i++) fa[i] = i;}
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void hebing(int x,int y){
x = find(x); y = find(y);
if(x == y) return;
if(size[y] > size[x]) swap(x,y);
size[x]+=size[y];
fa[y]=x;
}
}b;
int main(){
n = read(); m = read();
for(int i = 0; i < m; i++){
int u=read(),v=read(),w=read();
addedge(u,v,w);
}
b.ini();sort(e+1,e+m+1);
int k = 0,tot = 0;
for(int i = 1; i <= m; i++){
if(b.find(e[i].u) != b.find(e[i].v)){
b.hebing(e[i].u,e[i].v);
tot+=e[i].w;
k++;
}
if(k == n-1) break;
}
if(k!=n-1) cout<<"orz"<<endl;
else cout<<tot<<endl;
return 0;
}
回复
共 21 条回复,欢迎继续交流。
正在加载回复...