问
  • 板块学术版
  • 楼主WoodReal12
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/5/31 22:26
  • 上次更新2024/6/1 09:22:40
查看原帖
问
676569
WoodReal12楼主2024/5/31 22:26

为什么在这道最小生成树的题中,我用

#include <iostream>
#include <algorithm>
using namespace std;
struct bian{
	int u,v,w;
}a[10005];
int n,k;
int fa[2005];
bool cmp(bian x,bian y){
	return x.w<y.w;
}
int fnd(int u_){
	if(fa[u_]==u_)
		return fa[u_];
	return fa[u_]=fnd(fa[u_]);
}
void merge(int u_,int v_){
	fa[fnd(u_)]=fnd(v_);
}
int kruskal(){
	for(int i=1;i<2005;i++)
		fa[i]=i;
	sort(a+1,a+k+1,cmp);
	int res=0;
	for(int i=1;i<=k;i++){
		if(fnd(a[i].u)==fnd(a[i].v))
			continue;
		merge(a[i].u,a[i].v);
		res+=a[i].w;
	}
	return res;
}
int main(){
	cin>>n>>k;
	int ans=0;
	for(int i=1,op,u_,v_,w_;i<=k;i++){
		cin>>op>>u_>>v_>>w_;
		if(op==1)
			ans+=w_,merge(u_,v_);
		else
			a[i]={u_,v_,w_};
	}
	ans+=kruskal();
	cout<<ans<<endl;
    return 0;
} 	

会wa。

而把初始化fa数组放到主函数里却AC了?

ACcode:

#include <iostream>
#include <algorithm>
using namespace std;
struct bian{
	int u,v,w;
}a[10005];
int n,k;
int fa[2005];
bool cmp(bian x,bian y){
	return x.w<y.w;
}
int fnd(int u_){
	if(fa[u_]==u_)
		return fa[u_];
	return fa[u_]=fnd(fa[u_]);
}
void merge(int u_,int v_){
	fa[fnd(u_)]=fnd(v_);
}
int kruskal(){
	
	sort(a+1,a+k+1,cmp);
	int res=0;
	for(int i=1;i<=k;i++){
		if(fnd(a[i].u)==fnd(a[i].v))
			continue;
		merge(a[i].u,a[i].v);
		res+=a[i].w;
	}
	return res;
}
int main(){
	for(int i=1;i<2005;i++)
		fa[i]=i;
	cin>>n>>k;
	int ans=0;
	for(int i=1,op,u_,v_,w_;i<=k;i++){
		cin>>op>>u_>>v_>>w_;
		if(op==1)
			ans+=w_,merge(u_,v_);	
		else
			a[i]={u_,v_,w_};
	}
	ans+=kruskal();
	cout<<ans<<endl;
    return 0;
} 	
2024/5/31 22:26
加载中...