PKU 2377 Bad Cowtractors

http://poj.org/problem?id=2377
N個のノードにm個のコストの設定されたエッジがある。
最大全域木のコストを求めろという問題。ただし、全域木が作れない場合は-1を出力する。

最小全域木のソートを逆にすればおｋ。

pair<int,PI> edge[20000];
int un[1000];

int find(int x){
  if(un[x]==x)return x;
  else return un[x]=find(un[x]);
}

void unit(int a,int b){
  un[find(a)]=un[find(b)]=find(a);
}


main(){
  int n,m;
  cin>>n>>m;
  rep(i,n)un[i]=i;
  rep(i,m){
    int a,b,c;
    cin>>a>>b>>c;
    if(a>b)swap(a,b);
    edge[i]=mp(c,mp(a-1,b-1));
  }

  sort(edge,edge+m,greater<pair<int,PI> >());

  int ans=0;
  rep(i,m){
    if(find(edge[i].S.F)==find(edge[i].S.S))continue;
    ans+=edge[i].F;
    unit(edge[i].S.F,edge[i].S.S);
  }

  rep(i,n-1){
    if(find(i+1)==find(0))continue;
    ans=-1;
    break;
  }
  cout<<ans<<endl;
}