最小生成树kruskal算法44pts求调……

Lemon_zqp @ 2024-01-28 15:31:28

#include<bits/stdc++.h>
using namespace std;

int fa[5005];
double vis[5005];

struct node{
    int from, to, w;
};

vector<node> edge;

int find(int x){
    if(fa[x] == x){
        return x;
    }
    return (fa[x] = find(fa[x]));
}

void com(int a, int b){
    if(find(a) != find(b)){
        fa[a] = b;
    }
}

bool cmp(node x, node y){
    return x.w < y.w;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        fa[i] = i;
    }
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edge.push_back({a, b, c});
//      com(a, b);
    }
    sort(edge.begin(), edge.end(), cmp);
    int ans = 0, num = 0;
    for(int i = 0; i < m; i++){
        if(find(edge[i].from) != find(edge[i].to)){
            com(edge[i].to, edge[i].from);
            num++;
            ans += edge[i].w;
            if(num == n - 1) break;
//          cout << ans << " " << edge[i].w << endl; 
        }
    }
    if(num != n - 1) cout << "orz";
    else cout << ans;
    return 0;
}

by panxz2009 @ 2024-01-28 15:36:34

#include<bits/stdc++.h>
using namespace std;

int fa[5005];
double vis[5005];

struct node{
    int from, to, w;
};

vector<node> edge;

int find(int x){
    if(fa[x] == x){
        return x;
    }
    return (fa[x] = find(fa[x]));
}

void com(int a, int b){
    if(find(a) != find(b)){
        fa[a] = b;
    }
}

bool cmp(node x, node y){
    return x.w < y.w;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        fa[i] = i;
    }
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edge.push_back({a, b, c});
//      com(a, b);
    }
    sort(edge.begin(), edge.end(), cmp);
    int ans = 0, num = 0;
    for(int i = 0; i < m; i++){
        if(find(edge[i].from) != find(edge[i].to)){
            com(find(edge[i].to), find(edge[i].from));
            num++;
            ans += edge[i].w;
            if(num == n - 1) break;
//          cout << ans << " " << edge[i].w << endl; 
        }
    }
    if(num != n - 1) cout << "orz";
    else cout << ans;
    return 0;
}

改了第47行：

com(find(edge[i].to),find(edge[i].from));

by panxz2009 @ 2024-01-28 15:37:11

@Lemon_zqp 亲测能过

by Lemon_zqp @ 2024-01-28 16:36:16

@panxz2009 dalao,为啥要这么改啊……

by panxz2009 @ 2024-01-28 18:04:54

#include<bits/stdc++.h>
using namespace std;

int fa[5005];
double vis[5005];

struct node{
    int from, to, w;
};

vector<node> edge;

int find(int x){
    if(fa[x] == x){
        return x;
    }
    return (fa[x] = find(fa[x]));
}

void com(int a, int b){
    if(find(a) != find(b)){
        //fa[a] = b;                       //事实上是这一句有问题
        fa[find(a)]=fa[find(b)];
    }
}

bool cmp(node x, node y){
    return x.w < y.w;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        fa[i] = i;
    }
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        edge.push_back({a, b, c});
//      com(a, b);
    }
    sort(edge.begin(), edge.end(), cmp);
    int ans = 0, num = 0;
    for(int i = 0; i < m; i++){
        if(find(edge[i].from) != find(edge[i].to)){
            com(edge[i].to, edge[i].from);
            num++;
            ans += edge[i].w;
            if(num == n - 1) break;
//          cout << ans << " " << edge[i].w << endl; 
        }
    }
    if(num != n - 1) cout << "orz";
    else cout << ans;
    return 0;
}

by panxz2009 @ 2024-01-28 18:07:21

@Lemon_zqp

by panxz2009 @ 2024-01-28 18:11:24

我一开始那样改的话就是对于同一条边调用了两次 find 函数，第二次调用，也就是 21 行，反正是这个集合的父节点找自己，不影响，所以能过