POJ 2377 Bad Cowtractors 最小生成树 Kruskal

题目链接： POJ 2377 Bad Cowtractors
题目分析： 应该是求最大生成树，和最小生成树一样滴~
我用的Kruskal+并查集，Prim+堆应该也可以的

/************************************
Problem: 2377 User: ChenyangDu
Memory: 464K Time: 47MS
Language: C++ Result: Accepted
*************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

const int maxn = 1000+5,maxm = 20000+5;
int n,m,p[maxn];

struct edge{int s,t,w;}G[maxm];

int find(int a){
return a==p[a]?a:p[a] = find(p[a]);
}

void unite(int a,int b){
int fa = find(a),
        fb = find(b);
    p[fa] = fb;
}

edge Edge(int s,int t,int w){
    edge r;
    r.s = s;
    r.t = t;
    r.w = w;
return r;
}

bool cmp(edge a,edge b){
return a.w>b.w;
}

int main(){
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
        p[i] = i;
    }
for(int a,b,c,i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
        G[i] = Edge(a,b,c);
    }
    sort(G,G+m,cmp);
int ans = 0;
for(int i=0;i<m;i++){
        edge e = G[i];
if(find(e.s) != find(e.t)){
            unite(e.s,e.t);
            ans += e.w;
        }
    }
int root = find(1);
for(int i=2;i<=n;i++){
if(find(i) != root){
            ans = -1;
break;
        }
    }
cout<<ans<<endl;
return 0;
}