用kruskal做一堆mle和re,求调

P3366 【模板】最小生成树

slipknot @ 2022-07-26 16:29:52

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,sum=0,g=0;
bool book=0;
int f[114514];
struct huh{
    int u,v,w;
};
vector<huh> a;
bool cmp(huh a,huh b)
{
     return a.w<b.w;
}
int find(int v)
{
    if(f[v]==v)
    {
        return v;
    }
    else
    {
        f[v]=find(f[v]);
        return v;
    }
}

void hebing(int u,int v)
{
    int t1,t2;
    t1=find(u);
    t2=find(v);
    if(t1!=t2)
    {
        f[v]=t1;
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a.push_back(huh{x,y,z});
    }
    sort(a.begin(),a.end(),cmp);
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    for(int i=0;i<m;i++)
    {
        if(find(a[i].u)!=find(a[i].v))
        {
            g++;
            hebing(a[i].u,a[i].v);
            sum+=a[i].w;
        }
         if(g==n-1)
         {
            break;
         }
    }
    cout<<sum;

    return 0;
}

by letitdown @ 2022-07-26 16:33:44

find函数的else分支里面改成return f[v]

合并函数里面改成f[t2]=t1


by Waaifu_D @ 2022-07-26 16:34:33

@slipknot 您并查集错了,返回v干什么,还有根本没判断图是否连通


by slipknot @ 2022-07-26 16:37:54

@letitdown @waaifu_D 感谢大佬!


|