蒟蒻求助kruskal

Alexandra @ 2022-08-22 17:19:49

by Alexandra @ 2022-08-22 17:20:17

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 400010
struct fun
{
    int u;
    int v;
    int Next;
    int edge;
}a[N];
int fa[N],First[N];
int n,m,tot=-1;
inline void add(int x,int y,int z)
{
    a[++tot].v=y;
    a[tot].u=x;
    a[tot].Next=First[x];
    First[x]=tot;
    a[tot].edge=z;
}
bool cmp(fun wjl,fun szy)
{
    return wjl.edge<szy.edge;
}
int Find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=Find(fa[x]);
}
int kruskal()
{
    int ans=0,num=0;
    for(int i=1;i<=m;i++)
    {
        int x=a[i].u,y=a[i].v;
        int xx=Find(x),yy=Find(y);
        if(xx!=yy)
        {
            fa[xx]=yy;
            ans+=a[i].edge;
            num++;
        }
        if(num==n-1)return ans;
    }
    if(num!=n-1)return -1;
}
int main ()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z); 
    }
    sort(a+1,a+1+m,cmp);
    int ans=kruskal();
    if(ans==-1)printf("orz\n");
    else printf("%d\n",ans);

    return 0;
 } 

by CmsMartin @ 2022-08-22 17:25:10

@wangzl 扯淡。

by happybob @ 2022-08-22 17:26:56

@wangzl kruskal不是存边吗

by freoepn @ 2022-08-22 17:27:41

@Alexandra 试了一下，不建双向边有79

by Lavaloon @ 2022-08-22 17:28:20

将 sort 的 m 改成 2m , kruskal 的 m 改成 2m 就过了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 400010
struct fun
{
    int u;
    int v;
    int Next;
    int edge;
}a[N];
int fa[N],First[N];
int n,m,tot=-1;
inline void add(int x,int y,int z)
{
    a[++tot].v=y;
    a[tot].u=x;
    a[tot].Next=First[x];
    First[x]=tot;
    a[tot].edge=z;
}
bool cmp(fun wjl,fun szy)
{
    return wjl.edge<szy.edge;
}
int Find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=Find(fa[x]);
}
int kruskal()
{
    int ans=0,num=0;
    for(int i=1;i<=2*m;i++)
    {
        int x=a[i].u,y=a[i].v;
        int xx=Find(x),yy=Find(y);
        if(xx!=yy)
        {
            fa[xx]=yy;
            ans+=a[i].edge;
            num++;
        }
        if(num==n-1)return ans;
    }
    if(num!=n-1)return -1;
}
int main ()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z); 
    }
    sort(a+1,a+1+2*m,cmp);
    int ans=kruskal();
    if(ans==-1)printf("orz\n");
    else printf("%d\n",ans);

    return 0;
 } 

by freoepn @ 2022-08-22 17:30:17

tot起始值改为0，建单向边过了

by Lavaloon @ 2022-08-22 17:34:55

其实是不需要双向边的，改成单向边，统一 a 从 1 开始即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 400010
struct fun
{
    int u;
    int v;
    int Next;
    int edge;
}a[N];
int fa[N],First[N];
int n,m,tot=0;
inline void add(int x,int y,int z)
{
    a[++tot].v=y;
    a[tot].u=x;
    a[tot].Next=First[x];
    First[x]=tot;
    a[tot].edge=z;
}
bool cmp(fun wjl,fun szy)
{
    return wjl.edge<szy.edge;
}
int Find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=Find(fa[x]);
}
int kruskal()
{
    int ans=0,num=0;
    for(int i=1;i<=m;i++)
    {
        int x=a[i].u,y=a[i].v;
        int xx=Find(x),yy=Find(y);
        if(xx!=yy)
        {
            fa[xx]=yy;
            ans+=a[i].edge;
            num++;
        }
        if(num==n-1)return ans;
    }
    if(num!=n-1)return -1;
}
int main ()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    sort(a+1,a+1+m,cmp);
    int ans=kruskal();
    if(ans==-1)printf("orz\n");
    else printf("%d\n",ans);

    return 0;
 } 

by Alexandra @ 2022-08-22 17:34:59

@qujunyi @Lavaloon 谢谢大佬，邻接表出错了，已经过了