求助大佬，死活看不出哪里错了，用的Kruskal

xuan132 @ 2021-12-20 21:21:00

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct bian
{
    int head,tail,length;   
};
bool cmp(bian x,bian y)
{
    return x.length<y.length;
}
int v[10000];
long long sum=0;
bian l[1000000];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>l[i].head>>l[i].tail>>l[i].length;
    }
    sort(l+1,l+m,cmp);
    for(int i=1;i<=n;i++)
    {
        v[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int v1=l[i].head,v2=l[i].tail;
        if(v[v1]!=v[v2])
        {
            sum+=l[i].length;
            for(int i=1;i<=n;i++)
            {
                if(v[i]==v[v2])v[i]=v[v1];
            }
        }
    }
    cout<<sum;
    return 0;
}

by zhiyangfan @ 2021-12-20 21:25:21

@xuan132 并查集不是这么写的啊。

需要有 getf 函数：

int getf(int x) { return f[x] == x ? f[x] : f[x] = getf(f[x]); }

by Universal_xtr @ 2021-12-20 22:01:00

@xuan132 兄弟你的并查集呢

by Universal_xtr @ 2021-12-20 22:02:30

@xuan132 要有找祖宗的fa函数吧。。。

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

by Universal_xtr @ 2021-12-20 22:07:46

@xuan132

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
struct bian
{
    int head,tail,length;   
};
bool cmp(bian x,bian y)
{
    return x.length<y.length;
}
int v[10000];
int fa(int x){return v[x]==x?x:v[x]=fa(v[x]);}
long long sum=0,cnt=0;
bian l[1000000];
int main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>l[i].head>>l[i].tail>>l[i].length;
    }
    sort(l+1,l+m,cmp);
    for(int i=1;i<=n;i++)
    {
        v[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int v1=fa(l[i].head),v2=fa(l[i].tail);
        if(v1!=v2)
        {
            sum+=l[i].length;
            v[v1]=v[v2];
            cnt++;
            if(cnt==n-1)
            {
                break;
            }
        }
    }
    if(cnt==n-1)
    {
        cout<<sum;
    }
    else
    {
        cout<<"orz";
    }
    return 0;
}

by xuan132 @ 2021-12-20 22:59:06

@zhiyangfan 谢谢大佬

by xuan132 @ 2021-12-20 23:00:08

@Universal_xtr 谢谢大佬，还帮忙改了，感激涕零

by KS_tips_CN @ 2022-02-27 15:21:45

sort确定没有问题吗

我记得从1到m排序的话是

sort(a+1,a+1+m,cmp);

吧