最小生成树0分求助

DX3906_ourstar @ 2024-10-15 13:42:09

#include<iostream>
#include<algorithm>
#define re register
#define int long long
using namespace std;

const int N = 1e6 + 5;

int a,b,cnt,ans;
int fa[N];

struct edge{
    int u,v,w;
}e[N];

inline int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline bool cmp(edge a,edge b){
    return a.w < b.w;
}

inline void add(int u,int v,int w){
    cnt ++;
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    return ;
}

inline void cs(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(re int i = 1;i <= N;i ++){
        fa[i] = i;
    }
    return ;
}

signed main(){
    cs();
    cin>>a>>b;
    add(1,2,a);
    add(2,3,b);
    sort(e + 1,e + 3,cmp);
    for(re int i = 1;i <= 2;i ++){
        int x = find(e[i].u);
        int y = find(e[i].v);
        if(x != y){
            ans += e[i].w;
            fa[x] = y;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

by wcy110614 @ 2024-10-15 13:58:51

@DX3906_ourstar 解决了

#include<iostream>
#include<algorithm>
#define re register
#define int long long
using namespace std;

const int N = 1e6 + 5;

int a,b,cnt,ans;
int fa[N];

struct edge{
    int u,v,w;
}e[N];

inline int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline bool cmp(edge a,edge b){
    return a.w < b.w;
}

inline void add(int u,int v,int w){
    cnt ++;
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    return ;
}

inline void cs(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(re int i = 1;i <= N;i ++){
        fa[i] = i;
    }
    return ;
}

signed main(){
    cs();
    cin>>a>>b;
    add(1,2,a);
    add(2,3,b);
    sort(e + 1,e + 3,cmp);
    ans=0;
    for(re int i = 1;i <= 2;i ++){
        int x = find(e[i].u);
        int y = find(e[i].v);
        if(x != y){
            ans += e[i].w;
            fa[x] = y;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

ans 初值。

by wcy110614 @ 2024-10-15 13:59:29

@wcy110614 加了一个 ans=0; 就好了

另外不要在这种东西上浪费太多时间吧。

by THE_Epsilon @ 2024-10-17 17:13:19

@wcy110614 我之前用这个测我的dij+堆优，还是很有用的，顺便帮我解决的线段树的问题

by Chen_zi_long @ 2024-10-18 20:33:00

不是，这题怎么用这么复杂的方法？？？

by DX3906_ourstar @ 2024-10-19 18:00:59

@Chen_zi_long 太久没打最小生成树了，练个手

by zhangbomingg @ 2024-10-20 11:27:55

@DX3906_ourstar

6.

by xzh_2013 @ 2024-10-21 16:36:25

红题给各位玩出了黄题

by LiuCarry @ 2024-12-25 16:51:20

@DX3906_ourstar 不是什么ans=0的问题，实际上你代码中给fa初始化的部分循环是从1到N，而你fa数组只开了N个，下标爆了

by LiuCarry @ 2024-12-25 16:51:29

@DX3906_ourstar