有没有 大佬看一下哪错了qwq
查看原帖
有没有 大佬看一下哪错了qwq
559503
j_steady楼主2021/12/18 10:44
#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;
}
2021/12/18 10:44
加载中...