1 条题解

  • 0
    @ 2021-03-28 13:35:31
    #include<bits/stdc++.h>
    using namespace std;
    int n,m,q[6000];
    struct orz{
        int x,y,z,save;
    }a[210000];
    int sto(orz a,orz b)
    {
        return a.z < b.z;
    }
    int work(int x,int y)
    {
        while(q[q[x]] != q[x]) q[x] = q[q[x]];
        while(q[q[y]] != q[y]) q[y] = q[q[y]];
        if(q[x] == q[y]) return 1;
        else
        {
            q[q[y]] = q[x];
            return 0;
        }
    }
    int main()
    {
        long long ans = 0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) q[i]=i;
        for(int i=1; i<=m; i++) 
        {
            cin>>a[i].x>>a[i].y>>a[i].z;
            ans += a[i].z;
        }
        sort(a+1,a+m+1,sto);
        for(int i=1;i<=m;i++)
        {
            if(!work(a[i].x,a[i].y)) ans -= a[i].z;
        }
        cout << ans;
        return 0;
    }
    
  • 1

信息

难度
8
分类
(无)
标签
递交数
12
已通过
5
通过率
42%
上传者