PKU 2421 Constructing Roads

http://poj.org/problem?id=2421
n個の村があって、村iから村jまでの道の建設にはcijのコストがかかる。
いますでにm個の道が作られている時、村全体を行き来できるように道路を建設する最小のコストはいくらかを求める問題。

最小全域木。

int un[100];

int find(int x){
  if(un[x]==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;
  cin>>n;
  priority_queue<pair<int,PI> > Q;
  rep(i,n){
    un[i]=i;
    rep(j,n){
      int c;
      cin>>c;
      Q.push(mp(-c,mp(i,j)));
    }
  }
  int m;
  cin>>m;
  rep(i,m){
    int a,b;
    cin>>a>>b;
    unit(a-1,b-1);
  }
  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);
  }
  cout<<ans<<endl;
}