14 solutions

  • -5
    @ 2021-5-17 22:34:16

    注意:

    • 不要把洛谷AC代码移过来,注意数据范围
    • 不要用int!!

    不要复制下面的代码

    #include<bits/stdc++.h>
    using namespace std;
    int n,m;
    struct Edge{
    int u,v;
    long long len;
    }e[2000₁0];
    
    bool cmp(Edge a,Edge b){
    return a.len<=b.len;
    }
    int fa[100010];
    void init(){
    for(int i=1;i<=n;i++)fa[i]=i;
    }
    int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
    }
    void merge(int x,int y){
    x=get(x);
    y=get(y);
    if(x!=y){
    fa[x]=y;
    }
    }
    int kruskal(int n,int m){
    long long sum=0;
    init();
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++){
    int fu=get(e[i].u);
    int fv=get(e[i].v);
    if(fu!=fv){
    fa[fv]=fu;
    sum+=e[i].len;
    }
    }
    return sum;
    }
    int mian(){
    cin>>n>>m;
    for(int i=0;i<m;++i)cin>>e[i].u>>e[i].v>>e[i].len;
    cout<<kruskal(n,m)<<endl;
    return 0;
    }
    

    Information

    ID
    91
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    3
    Tags
    # Submissions
    857
    Accepted
    279
    Uploaded By