Help me understand the code please!

jumper007 (435)
Problem Statement

The greatest king of all times, Michael IV, is going to make big changes in his kingdom. The kingdom is composed of N cities (for simplicity numbered from 0 to N-1). Some pairs of cities are connected by bidirectional roads. We say that there is a path between different cities A and B if there exists a sequence of unique cities {C1, C2, ..., CM}, such that C1 = A and CM = B and for each index i < M, there is a road between cities Ci and Ci+1.

The current state of the kingdom is miserable. Some pairs of cities are not connected by any path. On the other hand, other pairs of cities are connected by multiple different paths, and that leads to complicated traffic routing. Michael wants to build some new roads and destroy some of the already existing roads in the kingdom so that after the reconstruction there will exist exactly one path between every pair of distinct cities. As building new roads and destroying old ones costs a lot of money, Michael wants to minimize the total cost spent on the reconstruction.



You are given a String[] kingdom describing the current state of the kingdom. There is a road between the cities i and j if and only if kingdom[i][j] = '1' and kingdom[j][i] = '1'. You are also given a String[] build and a String[] destroy. If no road exists between cities i and j, then the cost of building it is encoded by build[i][j]. If there already is a road between cities i and j, then the cost of destroying it is encoded by destroy[i][j]. The costs in both String[]s are encoded as characters, where 'A', 'B', ..., 'Z' represent the costs 0, 1, ..., 25, respectively and 'a', 'b', ..., 'z' represent the costs 26, 27, ..., 51, respectively. Your task is to find and return the minimal cost needed for the kingdom reconstruction.

Definition

Class: KingdomReorganization
Method: getCost
Parameters: String[], String[], String[]
Returns: int
Method signature: int getCost(String[] kingdom, String[] build, String[] destroy)
(be sure your method is public)


Notes
- N, the number of cities in the kingdom can be determined as the number of elements of kingdom.
- Two paths {A1, A2, ..., AR} and {B1, B2, ..., BS} are considered different if either R is not equal to S or there exists i <= R, such that Ai is not equal to Bi.
- There can never exist a road leading from some city to itself.
- The values in build that correspond to existing roads can simply be ignored. Similarly, ignore the values in destroy that correspond to nonexistent roads.

Constraints
- N will be between 1 and 50, inclusive.
- kingdom, build and destroy will each contain N elements.
- Each of the elements of kingdom, build and destroy will contain N characters.
- Each character in each element of kingdom will be either '0' or '1'.
- For each i, kingdom[i][i] will be '0'.
- For each i and j, kingdom[i][j] will be equal to kingdom[j][i].
- Each character in each element of build and destroy will be either an uppercase letter ('A'-'Z') or a lowercase letter ('a'-'z').
- For each i, build[i][i] and destroy[i][i] will be 'A'.
- For each i and j, build[i][j] will be equal to build[j][i].
- For each i and j, destroy[i][j] will be equal to destroy[j][i].

Examples
0)

{"000","000","000"}
{"ABD","BAC","DCA"}
{"ABD","BAC","DCA"}
Returns: 3
There are three cities in the kingdom, totally disconnected.

The only optimal solution is to build the roads between cities 0-1 (cost 1) and 1-2 (cost 2).
1)

{"011","101","110"}
{"ABD","BAC","DCA"}
{"ABD","BAC","DCA"}
Returns: 1
Now the three cities form a connected triangle and we need to destroy one road.

Optimal solution is to destroy the road between the cities 0-1 (cost 1).
2)

{"011000","101000","110000","000011","000101","000110"}
{"ABDFFF","BACFFF","DCAFFF","FFFABD","FFFBAC","FFFDCA"}
{"ABDFFF","BACFFF","DCAFFF","FFFABD","FFFBAC","FFFDCA"}
Returns: 7
We have six cities forming two separate triangles.

Like in the Example 1, destroy one road in each triangle (costs 1 for each road) and then join the triangles by a new road (costs 5).
3)

{"0"}
{"A"}
{"A"}
Returns: 0
One city is okay just as it is.
4)

{"0001","0001","0001","1110"}
{"AfOj","fAcC","OcAP","jCPA"}
{"AWFH","WAxU","FxAV","HUVA"}
Returns: 0
We have four cities, which are connected in such a way that there is exactly one path between each two cities.

Thus there is nothing to reconstruct.
5)

{"0000000000","0000000011","0001010000","0010010000","0000001000","0011000000","0000100000","0000000011","0100000101","0100000110"}
{"AhPEqkSFMM","hAfKPtsDad","PfAyGQkaqN","EKyAeLpRpm","qPGeASfNwo","ktQLSAnCAK","SskpfnAdJS","FDaRNCdAZz","MaqpwAJZAn","MdNmoKSznA"}
{"AgTqWWxEYH","gAXPgjzIRA","TXAleTmWvT","qPlAQkwxRO","WgeQAqgbJJ","WjTkqAiTzl","xzmwgiAuHb","EIWxbTuAwk","YRvRJzHwAn","HATOJlbknA"}
Returns: 65

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
#include <iostream> 
#include <cstdio> 
#include <cstring> 
#include <cstdlib> 
#include <vector> 
#include <string> 
#include <algorithm> 
using namespace std; 

struct disjoin_set{ 
  int parent[55], rank[55]; 
  int Find(int x){ 
    if (parent[x] != x)  parent[x] = Find(parent[x]); 
    return parent[x]; 
  } 
  void MakeSet(int id){ 
    parent[id] = id; 
    rank[id] = 1; 
  } 
  void Union(int x, int y){ 
    int xRoot = Find(x); 
    int yRoot = Find(y); 
    if (xRoot == yRoot) return; 
    if (rank[xRoot] < rank[yRoot]) 
      parent[xRoot] = yRoot; 
    else if (rank[yRoot] < rank[xRoot]) 
      parent[yRoot] = xRoot; 
    else{ 
      parent[yRoot] = xRoot; 
      rank[xRoot]++; 
    } 
  } 
}; 

struct node{ 
  int x, y, l; 
  node(){} 
  node(int xx, int yy, int ll){ 
    x = xx; y = yy; l = ll; 
  } 
}; 

bool cmp1(const node &a, const node &b){ 
  return a.l > b.l; 
} 

bool cmp2(const node &a, const node &b){ 
  return a.l < b.l; 
} 

class KingdomReorganization{ 
public: 
  int cost(char ch){ 
    if ('A' <= ch && ch <= 'Z') 
      return ch - 'A'; 
    else 
      return ch - 'a' + 26; 
  } 
  int getCost(vector <string> kingdom, vector <string> build, vector <string> destroy){ 
    vector<node> E1, E2; 
    int n = kingdom.size(); 
    for (int i = 0; i < n; i++) 
      for (int j = 0; j < i; j++) 
        if (kingdom[i][j] == '1') 
          E1.push_back(node(i, j, cost(destroy[i][j]))); 
        else 
          E2.push_back(node(i, j, cost(build[i][j]))); 
    disjoin_set S; 
    for (int i = 0; i < n; i++) 
      S.MakeSet(i); 
    vector<node>::iterator ii; 
    int cost = 0; 
    sort(E1.begin(), E1.end(), cmp1); 
    for (ii = E1.begin(); ii != E1.end(); ii++) 
      if (S.Find(ii->x) != S.Find(ii->y)) 
        S.Union(ii->x, ii->y); 
      else 
        cost += ii->l; 
    sort(E2.begin(), E2.end(), cmp2); 
    for (ii = E2.begin(); ii != E2.end(); ii++) 
      if (S.Find(ii->x) != S.Find(ii->y)){ 
        S.Union(ii->x, ii->y); 
        cost += ii->l; 
      } 
    return cost; 
  } 
};



I got to understand the Graph Theory. Can someone explain it to me ?

------------------------------
This code has been written by someone else and it's not mine. The code works perfectly for any data set entered and gained 100% score.
------------------------------
Last edited on
Cubbi (4774)
This problem is discussed, along with other problems from that match, at http://apps.topcoder.com/wiki/display/tc/SRM+531
(and yes, basic graph theory helps a lot at topcoder). The discussion has links to the concepts and algorithms mentioned.
Last edited on
jumper007 (435)
Thanks, but can someone still link me to a tutorial on Graph Theory ?
cnoeval (643)
jumper007 (435)
I was thinking of an explanation... but thanks anyway... I guess I'll have to ask my math teacher >.>
Topic archived. No new replies allowed.