SRM531 Div2 Hard

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

kruskalを知っていれば簡単。

view plainprint?

1. class DisjointSet{  
2. public:   
3.   vector<int> rank, p;  
4.   DisjointSet(int size){  
5.     rank.resize(size, 0);  
6.     p.resize(size, 0);  
7.   }  
8.   void make(int a){  
9.     rank[a] = 0;  
10.     p[a] = a;  
11.   }  
12.   void join(int a, int b){  
13.     link(find(a), find(b));  
14.   }  
15.   int find(int a){  
16.     return (a == p[a])? a : p[a] = find(p[a]);  
17.   }  
18.   bool isSameSet(int a, int b){  
19.     return find(a) == find(b);  
20.   }  
21.   void link (int a, int b){  
22.     if(rank[a] > rank[b])  
23.       p[b] = a;  
24.     else{  
25.       p[a] = b;  
26.       if(rank[a] == rank[b])  
27.         rank[b]++;  
28.     }  
29.   }  
30. };  
31.   
32. int no(char c)  
33. {  
34.   if ('A' <= c && c <= 'Z') return c - 'A';  
35.   if ('a' <= c && c <= 'z') return c - 'a' + 26;  
36.   return -100;  
37. }  
38.   
39. class KingdomReorganization {  
40. public:  
41.   int getCost(vector <string> K, vector <string> B, vector <string> D)   
42.   {  
43.     const int N = K.size();  
44.     DisjointSet ds(N);  
45.   
46.     for (int i = 0; i < N; ++i) {  
47.       ds.make(i);  
48.     }  
49.   
50.     vector< pair<int, pair<int, int> > > v, u;  
51.     for (int i = 0; i < N; ++i) {  
52.       for (int j = i + 1; j < N; ++j) {  
53.         if (K[i][j] == '0') {  
54.           v.push_back(make_pair(no(B[i][j]), make_pair(i, j)));  
55.         } else {  
56.           u.push_back(make_pair(no(D[i][j]), make_pair(i, j)));  
57.         }  
58.       }  
59.     }  
60.     sort(v.begin(), v.end());  
61.     sort(u.begin(), u.end());  
62.     reverse(u.begin(), u.end());  
63.   
64.     int sum = 0;  
65.   
66.     for (int i = 0; i < u.size(); ++i) {  
67.       pair<int, int> p = u[i].second;  
68.       if (!ds.isSameSet(p.first, p.second)) {  
69.         ds.join(p.first, p.second);  
70.       } else sum += u[i].first;  
71.     }  
72.       
73.     for (int i = 0; i < v.size(); ++i) {  
74.       pair<int, int> p = v[i].second;  
75.       if (!ds.isSameSet(p.first, p.second)) {  
76.         ds.join(p.first, p.second);  
77.         sum += v[i].first;  
78.       }   
79.     }  
80.         
81.     return sum;  
82.   }  
83.   
84. };  

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;
  }

};