PKU 1861 Network

http://poj.org/problem?id=1861
n個のノードを結ぶ辺が与えられる。
これらの辺から最大の長さの辺が最小になるように全域木を作り、つかった辺などを出力するというような物。

時間そこそこギリギリで通りました。
最小全域木ですね。

int un[1000];

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

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

main(){
  int n,m;
  cin>>n>>m;
  priority_queue<pair<int,PI> > q;
  rep(i,n)un[i]=i;
  rep(i,m){
    int a,b,c;
    cin>>a>>b>>c;
    q.push(mp(-c,mp(a-1,b-1)));
  }
  vector<PI> P;

  int ans=0;
  while(!q.empty()){
    int c=-q.top().F,a=q.top().S.F,b=q.top().S.S;
    q.pop();
    if(find(a)==find(b))continue;
    ans=c;
    unit(a,b);
    P.pb(mp(a+1,b+1));
  }
  cout<<ans<<endl;
  cout<<SZ(P)<<endl;
  rep(i,SZ(P))cout<<P[i].F<<' '<<P[i].S<<endl;
}