P3366为什么3个点re

P3366 【模板】最小生成树

__gcd__ @ 2021-09-11 22:38:29

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int a,b,c;
}s[11000];
int f[11000];
int cmp(node n1,node n2){
    if(n1.c<n2.c)
      return 1;
    return 0;
}
int find(int x){
    if(f[x]!=x)
      return f[x]=find(f[x]);
    else
      return x;
}
int main(){
    int n,m,x,y,ans=0,t=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      f[i]=i;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
    sort(s+1,s+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int fx=find(s[i].a),fy=find(s[i].b);
        if(fx!=fy){
            ans+=s[i].c;
            f[fx]=fy;
            t++;
            if(t==n-1)
            {
                cout<<ans;
                return 0;
            }
        }
    }
    cout<<"orz";
}

by chengch @ 2021-09-11 22:49:47

数组要开200005


|