Kruskal 没过样例
查看原帖
Kruskal 没过样例
293527
风人楼主2020/5/10 09:16

好像并查集有点问题,但改不出来,求助

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Node{
    int x;
    int y;
    int lenth;
}a[200005];

bool cmp(Node  x, Node y){ return x.lenth<y.lenth;}
int getfather(int);
inline void kruskal();

int n,m,k1,k2,k3,tot;
int father[5005];
long long ans;

int main(){
    ios::sync_with_stdio(0);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) father[i] = i;
    for(int i = 1;i <= m;i++)
        cin >> a[i].x >> a[i].y >>a[i].lenth;
    sort(a+1,a+m+1,cmp);
    kruskal();
    if (tot < n-1){
        cout << "orz";
        return 0;
    }
    cout << ans;
    return 0;
}

int getfather(int k){
    if (father[k] == k) return k;
    father[k] = getfather(father[k]);
    return father[k];
}

inline void kruskal(){
    for (int i = 1;i <= m; i++){
        if (getfather(a[i].x) == getfather(a[i].y)) continue;
        ans += a[i].lenth;
        father[a[i].x] = a[i].y;
        tot ++;
        cout <<tot;
        if(tot == n-1) break;
    }
}
2020/5/10 09:16
加载中...