56分kruskal求助

qscisQJing @ 2022-04-14 11:45:01

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
int n,m,ans,cnt;int fa[MAXN];
struct edge
{
    int u,v,w;
}ed[200005];
bool cmp(edge x,edge y){return x.w<=y.w;}
int find(int x)
{
    if(x!=fa[x])fa[x]=find(fa[x]);
    return fa[x];
}
void work()
{
    sort(ed,ed+m,cmp);
    for(int i=0;i<m;i++)
    {

        int fau=find(ed[i].u),fav=find(ed[i].v);
        if(fau==fav)
            continue;
        ans+=ed[i].w;
        fa[fau]=fav;
        if(++cnt==n-1)break;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)fa[i]=i;
    for(int i=0;i<m;i++)
        cin>>ed[i].u>>ed[i].v>>ed[i].w;
    //  for(int i=0;i<m;i++)cout<<link[i].w;
    work();
    cout<<ans;
    return 0;
}

by PPL_ @ 2022-04-14 11:54:18

@qscisQJing sort 要严格偏序关系才行，用 <= 重载 < 会出现 a<b 且 b<a 的情况，就会出现 RE 之类的错误。

by j1ANGFeng @ 2022-04-14 12:59:42

@qscisQJing

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+5;
int n,m,ans,cnt;int fa[MAXN];
struct edge
{
    int u,v,w;
}ed[200005];
bool cmp(edge x,edge y){return x.w<y.w;}
int find(int x)
{
    if(x!=fa[x])fa[x]=find(fa[x]);
    return fa[x];
}
void work()
{
    sort(ed,ed+m,cmp);
    for(int i=0;i<m;i++)
    {

        int fau=find(ed[i].u),fav=find(ed[i].v);
        if(fau==fav)
            continue;
        ans+=ed[i].w;
        fa[fau]=fav;
        if(++cnt==n-1)break;
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)fa[i]=i;
    for(int i=0;i<m;i++)
        cin>>ed[i].u>>ed[i].v>>ed[i].w;
    //  for(int i=0;i<m;i++)cout<<link[i].w;
    work();
    if(cnt!=n-1)
      cout<<"orz";
    else
    cout<<ans;
    return 0;
}

A了

by Revdream @ 2022-04-14 13:09:06

@qscisQJing 因为cmp(x,x)必须返回false

by qscisQJing @ 2022-04-14 14:14:18

感谢dalao