14分求调 kruskal

Three_no @ 2023-11-27 13:26:54

#include<bits/stdc++.h>
using namespace std;
int mincost,cost,s1;
int f[5010],s,t,j,n,m,ans;
int find(int x){
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
struct Edge{
    int a,b,w;
}edge[5010];
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int main(){
    cin>>n>>m;

    for(int i=1;i<=m;i++){
        cin>>s>>t>>cost;
        edge[i]={s,t,cost};
    }
    sort(edge+1,edge+1+j,cmp);
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=m;i++){

        int fx=find(edge[i].a);
        int fy=find(edge[i].b);
        if(fx!=fy){
            ans++;
            mincost+=edge[i].w;
            f[fx]=fy;
        }
        if(ans==n-1) break;
    }
    cout<<mincost<<endl;

    return 0;
} 

by hyx_0704 @ 2023-11-27 13:31:50

M<=2e5

by hyx_0704 @ 2023-11-27 13:32:30

这个不re也是挺厉害的

by Three_no @ 2023-11-27 13:40:56

@hyx_0704 thx%%%

by Three_no @ 2023-11-27 13:45:36

@hyx_0704 请问怎么改呢

我把数组开大，但还是不行

#include<cstdio>
#include<algorithm>
using namespace std;
int mincost,cost,s1;
int f[5010],s,t,j,n,m,ans;
int find(int x){
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
struct Edge{
    int a,b,w;
}edge[200005];
bool cmp(Edge a,Edge b){
    return a.w<b.w;
}
int main(){
    scanf("%d%d", &n, &m);

    for(int i=1;i<=m;i++){
        scanf("%d%d%d", &s, &t, &cost);
        edge[i]={s,t,cost};
    }
    sort(edge+1,edge+1+j,cmp);
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=m;i++){

        int fx=find(edge[i].a);
        int fy=find(edge[i].b);
        if(fx!=fy){
            ans++;
            mincost+=edge[i].w;
            f[fx]=fy;
        }
        if(ans==n-1) break;
    }
    printf("%d",mincost);

    return 0;
} 

by Down_syndrome @ 2023-11-27 13:52:36

注意看你的排序，+j是什么东西，j是0，等同于你没有排序

by hyx_0704 @ 2023-11-27 13:59:24

sort(e+1,e+m+1,cmp)

by hyx_0704 @ 2023-11-27 14:03:36

@Rannan2000 建议编译开 -Wall 没用的变量会警告的

by Three_no @ 2023-11-28 12:35:19

@c20220625 @hyx_0704 谢谢

这个代码是我改的另一道题的代码，结果那里忘记改了（doge