F1NE @ 2024-08-24 16:24:33
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;
}
by Manki233 @ 2024-08-24 16:32:30
@MYXaoiing
for(int i=1,x,y;i<=M&&cnt<N;i++){ // || -> &&
by small_moon @ 2024-08-24 16:32:43
for(int i=1,x,y;i<=M||cnt<N;i++)
改为
for(int i=1,x,y;i<=M;i++)
就能过。。。原因不清楚
by F1NE @ 2024-08-24 16:33:10
@Manki233 谢谢
by Qinglan2011 @ 2024-08-24 16:33:29
(int i=1,x,y;i<=M;i++)用这个
by Qinglan2011 @ 2024-08-24 16:34:03
@MYXaoiing