SRM531 Div2 Hard

950
既にある辺を使って最大全域森を作る。
その後は、新たな辺を付け足して連結にする。

kruskalを知っていれば簡単。

class DisjointSet{
public: 
  vector<int> rank, p;
  DisjointSet(int size){
    rank.resize(size, 0);
    p.resize(size, 0);
  }
  void make(int a){
    rank[a] = 0;
    p[a] = a;
  }
  void join(int a, int b){
    link(find(a), find(b));
  }
  int find(int a){
    return (a == p[a])? a : p[a] = find(p[a]);
  }
  bool isSameSet(int a, int b){
    return find(a) == find(b);
  }
  void link (int a, int b){
    if(rank[a] > rank[b])
      p[b] = a;
    else{
      p[a] = b;
      if(rank[a] == rank[b])
        rank[b]++;
    }
  }
};

int no(char c)
{
  if ('A' <= c && c <= 'Z') return c - 'A';
  if ('a' <= c && c <= 'z') return c - 'a' + 26;
  return -100;
}

class KingdomReorganization {
public:
  int getCost(vector <string> K, vector <string> B, vector <string> D) 
  {
    const int N = K.size();
    DisjointSet ds(N);

    for (int i = 0; i < N; ++i) {
      ds.make(i);
    }

    vector< pair<int, pair<int, int> > > v, u;
    for (int i = 0; i < N; ++i) {
      for (int j = i + 1; j < N; ++j) {
        if (K[i][j] == '0') {
          v.push_back(make_pair(no(B[i][j]), make_pair(i, j)));
        } else {
          u.push_back(make_pair(no(D[i][j]), make_pair(i, j)));
        }
      }
    }
    sort(v.begin(), v.end());
    sort(u.begin(), u.end());
    reverse(u.begin(), u.end());

    int sum = 0;

    for (int i = 0; i < u.size(); ++i) {
      pair<int, int> p = u[i].second;
      if (!ds.isSameSet(p.first, p.second)) {
        ds.join(p.first, p.second);
      } else sum += u[i].first;
    }
    
    for (int i = 0; i < v.size(); ++i) {
      pair<int, int> p = v[i].second;
      if (!ds.isSameSet(p.first, p.second)) {
        ds.join(p.first, p.second);
        sum += v[i].first;
      } 
    }
      
    return sum;
  }

};