静かで孤独な日記

のんびりたまに

AOJ 2511 Sinking islands

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;

//union_find
//_n mast be unsigned int
//BEGIN CUT HERE
class union_find{
public:
    explicit union_find(int _n):n(_n){
        par.resize(static_cast<unsigned long>(_n));
        rank.resize(static_cast<unsigned long>(_n));
        sizes.resize(static_cast<unsigned long>(_n));
        for(int i=0;i<_n;i++){
            par[i]=i;
            rank[i]=0;
            sizes[i]=1;
        }
    }
    
    //親ノードを見つけます
    int find(int a){
        if(par[a]==a)return a;
        return par[a]=find(par[a]);
    }
    
    //aとbが同じグループかの判定
    bool same(int a,int b){
        return find(a)==find(b);
    }
    
    //aとbを同じグループにします
    void unite(int a,int b){
        link(find(a),find(b));
    }
    
    //aが属するグループの要素数を求めます
    int size(int a){
        return sizes[find(a)];
    }
    
    //全体がどのグループに属しているかがわかります
    void view(){
        for(int i=0;i<n;i++){
            cout<<" par"<<"["<<i<<"]="<<par[i]<<((i==n-1)?"\n":",");
        }
        for(int i=0;i<n;i++){
            cout<<"size"<<"["<<i<<"]="<<sizes[i]<<((i==n-1)?"\n":",");
        }
        cout<<endl;
    }

    void init(){
      for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
        sizes[i]=1;
      }
    }

private:
    void link(int a,int b){
        if(same(a,b))return;
        if(rank[a]>rank[b]){
            par[b]=a;
            sizes[a]+=sizes[b];
            sizes[b]=0;
        }else{
            par[a]=b;
            if(rank[a]==rank[b])rank[b]++;
            sizes[b]+=sizes[a];
            sizes[a]=0;
        }
    }
    int n;
    vector<int> par;
    vector<int> rank;
    vector<int> sizes;
};

int main(){
  int n,m;
  while(cin>>n>>m,n){
    vector<pair<int,int> > h;
    for(int i=0;i<n;i++){
      int a;cin>>a;
      h.push_back({a,i});
    }
    union_find tmp(n);
    vector<pair<pair<int,int>,int> > v;
    for(int i=0;i<m;i++){
      int a,b,c;cin>>a>>b>>c;
      a--;b--;
      tmp.unite(a,b);
      v.push_back(make_pair(make_pair(c,a),b));
    }
    if(tmp.size(0)!=n){
      cout<<0<<endl;
      continue;
    }
    sort(h.begin(),h.end());
    reverse(h.begin(),h.end());
    sort(v.begin(),v.end());
    union_find uf(n);
    ll ans=0;
    bool ok[201];
    int cont=0;
    for(int i=0;i<n;i++)ok[i]=0;
    for(int i=0;i<n;i++){
      ok[h[i].se]=1;
      if(i==n-1 || h[i].fi!=h[i+1].fi){
        for(int j=0;j<m;j++){
          int nowa=v[j].fi.se;
          int nowb=v[j].se;
          if(ok[nowa] && ok[nowb] && !uf.same(nowa,nowb)){
            ans+=v[j].fi.fi;
            cont++;
            uf.unite(nowa,nowb);
          }
        }
        if(cont!=i){
          uf.init();
          cont=0;
          ans=0;
        }
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}
  • 日本語が難しかった。。
  • こういう問題に当たりたくないなぁ。。