BZOJ3390: [Usaco2004 Dec]Bad Cowtractors牛的报复

题目大意:

最大生成树裸题.

题解:

Kruskal,$O(mlogm)$.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 1010
#define M 100010
int r[N];
inline int find(int x){
    int q=x,rq;
    for(;x!=r[x];x=r[x]);
    for(;q!=x;rq=r[q],r[q]=x,q=rq);
    return x;
}
struct Edge{
    int u,v,l;
    Edge(){}
    Edge(int _u,int _v,int _l):u(_u),v(_v),l(_l){}
    bool operator<(const Edge&B)const{
        return l>B.l;
    }
}E[M];
int main(){
    int n,m,i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].l);
    sort(E+1,E+m+1);
    int ans=0,cnt=0;
    for(i=1;i<=n;++i)
        r[i]=i;
    int ra,rb;
    for(i=1;i<=m;++i){
        ra=find(E[i].u);
        rb=find(E[i].v);
        if(ra!=rb){
            ++cnt,ans+=E[i].l;
            r[ra]=rb;
        }
    }
    printf("%d\n",cnt==n-1?ans:-1);
    return 0;
}