写一个Kruskal怎么就RE了?

P3366 【模板】最小生成树

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


|