写一个Kruskal怎么就RE了?
查看原帖
写一个Kruskal怎么就RE了?
1163927
F1NE楼主2024/8/24 16:24

RE了#13。怀疑是并查集写错了,但是我没有证据

#include<bits/stdc++.h>
using namespace std;
const int MAXI=2e5+9,maxi=5e3+9;
int N,M,ufs[maxi],ans=0,cnt=1;
struct edge{
	int x,y,z;
}e[MAXI];
int fnd(int x){if(ufs[x]!=x) ufs[x]=fnd(ufs[x]);return ufs[x];}
inline void uni(int x,int y){if(fnd(x)!=fnd(y))ufs[fnd(y)]=fnd(x);return;}
inline bool pd(int x,int y){return fnd(x)==fnd(y);}
bool cmp(edge a,edge b){return a.z<b.z;}
int main(){
	cin>>N>>M;
	for(int i=1;i<=N;i++)ufs[i]=i;
	for(int i=1;i<=M;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
	sort(e+1,e+M+1,cmp);
//for(int i=1;i<=M;i++)printf("x[%d]=%d,y[%d]=%d,z[%d]=%d\n",i,e[i].x,i,e[i].y,i,e[i].z);
	for(int i=1,x,y;i<=M||cnt<N;i++){
		x=e[i].x,y=e[i].y;
		if(!pd(x,y)){
			uni(x,y);
			ans+=e[i].z;
			cnt++;
		}
//for(int i=1;i<=N;i++)printf("f[%d]=%d ",i,ufs[i]);cout<<endl;
	}
	if(cnt!=N) cout<<"orz";
	else cout<<ans;
	return 0;
} 
2024/8/24 16:24
加载中...