用kruskal86分re了1个点QwQ求助（本地对的）

tabuloforme @ 2022-08-11 10:47:36

#include<bits/stdc++.h>
using namespace std;
int f[10005],n,m;
long long sum=0;
struct M{
    int x,y,z;
}a[200005];
int cmp(M a,M b){
    return a.z<b.z;
}
int find(int a){
    if(f[a]!=a)f[a]=find(f[a]);
    return f[a];
}
void unionn(int a,int b){
    a=find(a);
    b=find(b);
    f[b]=a; 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
    for(int i=1;i<=10000;i++)f[i]=i;
    sort(a+1,a+m+1,cmp);
    int s=n;
    for(int i=1;i<=s-1;i++)
        if(find(a[i].x)!=find(a[i].y)){
            unionn(a[i].x,a[i].y);
            sum+=a[i].z;
        }
        else
        s++;
    int p=find(1);
    for(int j=2;j<=n;j++){
        int q=find(j);
        if(p!=q){
            cout<<"orz";
            return 0;
        }
    }
    cout<<sum;
return 0; 
} 

by ReTF @ 2022-08-11 10:56:09

@tabuloforme 数据有重边，运行时一直执行s++会爆栈。

改成这样即可AC。

#include<bits/stdc++.h>
using namespace std;
int f[200005],n,m;
long long sum=0;
struct M{
    int x,y,z;
}a[200005];
int cmp(M a,M b){
    return a.z<b.z;
}
int find(int a){
    if(f[a]!=a)f[a]=find(f[a]);
    return f[a];
}
void unionn(int a,int b){
    a=find(a);
    b=find(b);
    f[b]=a; 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
    for(int i=1;i<=n;i++)f[i]=i;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(find(a[i].x)!=find(a[i].y)){
            unionn(a[i].x,a[i].y);
            sum+=a[i].z;
        }
    }
    int p=find(1);
    for(int j=2;j<=n;j++){
        int q=find(j);
        if(p!=q){
            cout<<"orz";
            return 0;
        }
    }
    cout<<sum;
return 0; 
} 

by iiiiiyang @ 2022-08-11 10:59:01

@tabuloforme

   else
   s++;

应该是这个炸了

为什么不能写成 i<=m然后加个计数器判断连边到达n-1跳出呢

by tabuloforme @ 2022-08-11 11:00:20

谢谢大佬！ 此贴完结