有没有 大佬看一下哪错了qwq

j_steady @ 2021-12-18 10:44:33

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<iostream>
#define MAXN 200005

using namespace std;

int n,m,fa[MAXN];
struct edge{
    int u,v,w; 
}e[MAXN];
bool cmp (edge a,edge b){
    return a.w < b.w; 
}
void init(int n){
    for (int i=1;i<=n;i++){
        fa[i]=i;
    }
}
int find (int x){
    if (fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
//void join (int x,int y){
//  int f1=find (x),f2=find(y);
//  if(f1==f2) return;
//  else fa[f1]=f2;
//}

int t=0;
void add(int u,int v,int w){
    e[++t].u=u;
    e[t].v=v;
    e[t].w=w;
    //fa[e[t].v]=e[t].u;
}
int cnt =0;
int sum=0;
int main (){
    scanf ("%d%d",&n,&m);
    init(n);
    for (int i=1;i<=m;i++){
        int a,b,c;
        scanf ("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    sort (e+1,e+m+1,cmp);
    for (int i=1;i<=m;i++){
        int aa=find(e[i].u),bb=find(e[i].v);
        if (aa==bb) continue;
        else fa[aa]=bb;
        sum+=e[i].w;
        if (++cnt==n-1) break;
        }

    int ans=0;
    for (int i=1;i<=m;i++){
        if (find(i)==i) ans++;
    }
    if (ans > 1) printf ("orz");
    else printf ("%d",sum);
    return 0;
}

by K0stlin @ 2021-12-18 10:49:43

不要加反边

by kdy20100729 @ 2021-12-18 10:50:24

@j_steady

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,len,cnt,ans,sum,fa[10005];
struct node
{
    int x,y,len;
}edge[200005];
bool cmp(node x,node y)
{
    return x.len<y.len;
}
int find(int x)
{
    if (fa[x]==x)
        return x;
    return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if (fx!=fy)
    {
        cnt++;
        fa[fx]=fy;
    }
    return ;
}
void kruskal()
{
    sort(edge+1,edge+1+m,cmp);
    for(int i=1; i<=m; i++)
    {
        int x=find(edge[i].x);
        int y=find(edge[i].y);
        if (x!=y)
        {
            unionn(x,y);
            ans+=edge[i].len;
            if (cnt==n-1)
                break;
        }
    }
    return ;
}
signed main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        fa[i]=i;
    for(int i=1; i<=m; i++)
        cin >> edge[i].x >> edge[i].y >> edge[i].len;
    kruskal();
    for(int i=1; i<=n; i++)
        if (fa[i]==i)
            sum++;
    if (sum==1)
        cout << ans;
    else
        cout << "orz";
    return 0;
}

by 404Not_Found @ 2021-12-18 10:51:08

    for (int i=1;i<=m;i++){
        int a,b,c;
        scanf ("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }

去掉 add(b,a,c)。

by j_steady @ 2021-12-18 10:54:58

@404Not_Found 为什么加了反边会错qwq

by j_steady @ 2021-12-18 10:56:41

@Kostlin 谢谢orz

by 404Not_Found @ 2021-12-18 11:01:24

Kruskal 每条边只要知道两端点的信息。

并且你 sort 只 排序了前 m 条边，但你加了 2m 条，实际上你跑 Kruskal 只跑了一半的边。并且 Kruskal 是用并查集维护双向关系的，

by 404Not_Found @ 2021-12-18 11:02:56

@j_steady

by 404Not_Found @ 2021-12-18 11:03:29

Kruskal 要知道的只是边的连通性。

by j_steady @ 2021-12-18 11:10:12

@404Not_Found 懂了太强了！orz Thank you