问
  • 板块学术版
  • 楼主_QWQ__QWQ_
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/25 22:10
  • 上次更新2023/11/26 09:06:32
查看原帖
问
878137
_QWQ__QWQ_楼主2023/11/25 22:10

我的最小生成树模板代码有点问题,如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
int n,m;
struct Edge{
	int u,v,w;
}edge[maxn];
int fa[maxn];
bool cmp(Edge x,Edge y){
	return x.w<y.w;
}
int find(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=find(fa[x]);
} 
void uniset(int x,int y){
	x=find(x);
	y=find(y);
	if(x!=y){
		fa[x]=y;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		cin>>edge[i].u>>edge[i].v>>edge[i].w;
	}
	int ans=0,cnt=0;
	sort(edge+1,edge+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(fa[edge[i].u]!=fa[edge[i].v]){
			ans+=edge[i].w;
			uniset(edge[i].u,edge[i].v);
			cnt++;
		}
	}
	if(cnt!=n-1){
		cout<<"orz"<<endl;
		return 0;
	}
	cout<<ans<<endl;
	return 0;
}

该代码在以下数据中本来要输出的是7,可它的输出是orz。

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

但我将if(fa[edge[i].u]!=fa[edge[i].v])改成if(find(edge[i].u)!=find(edge[i].v))有什么问题吗

2023/11/25 22:10
加载中...