Link to problem statement
This problem is very simple, so much that I don't think an explanation would actually help. I think this is a great problem to solve alone when you are starting the path to programming, and I won't ruin that experience.
KingdomXCitiesandVillagesAnother
Link to problem statement
After solving some problems, this problem will give you a Minimum spanning Tree vibe. That is because the problem asks you to connect many things together in a way that the cost of connecting them all together is minimum. You would notice that the final connected result does not need to have cycles, because cycles would usually mean that you are doing more connections than necessary. The main difference though, is that you we are not allowed to connect cities together (because of the way the rules explained in the statement work) and it is not necessary to do it. We want to connect each village directly or indirectly to a city and nothing else. Basically, each city will end up being the center of a network of villages that are connected to the city and also to each other, directly or indirectly. Because there won't be cycles, each city will belong to a different tree. The solution will be a set of trees, a forest.
In problems that are initially so similar to the minimum spanning tree problem, it is usually a good idea to try to find a way to reduce the problem to the MST problem, because that is a known problem that is not so hard to implement. As mentioned, the main issue is that each city will have its own tree of villages attached to it. When connecting a village to a city, the rules described specify only that the cost to connect a village to the city is the minimum. How about simply considering all cities a single node? If all cities were joined together, all the trees in the forest will then become a single tree because they would all have the city node in common. The trick in here is to note that the distance between a village and this special city node is the minimum distance between the village and any city.
If we used this special city node instead of the cities, we could then use a MST algorithm to connect all the villages and the city node together in a single tree of minimum cost. Here comes some imagination: After this MST is found, you can return to the case that has many cities and a tree per city. Simply consider any resulting edge between a village and the special city node, and find a city whose cost to connect the village to it is the same as the cost of the edge picked to connect the village and the special city node, then replace the edge with one that connects the village to the normal city. This loosely allows us to see that the minimum spanning tree when there is a combined city node as we mentioned will also result in the minimum cost to solve the original problem.
There are other ways to see the problem, one is to consider all the cities already connected to each other. This means that the cost to connect the cities has already been considered and we do not have to include it in our calculation. We can translate this as there being many edges of cost 0 connecting the cities together. We can then, again, find the minimum spanning tree. After this, we can delete all of those cost 0 edges and we would find a forest as the one the original problem wants.
What is left is to implement the minimum spanning tree algorithm after creating the new graph that either contains those 0-cost edges or a single combined city node. The usual tools of the trade are Prim's algorithm or Kruskal's algorithm. For this problem, it does not really matter which of them you pick. I picked Kruskal by preference, it needs an efficient way to do union, but it is also useful sometimes when you need to find the minimum cost forest of n trees instead of the minimum cost tree. The c++ implementation follows:
#define for_each(q,v) for(typeof(v.begin()) q=v.begin(); q!=v.end(); q++)
struct KingdomXCitiesandVillagesAnother
{
// We use this for Kruskal's union find:
// Finds the grand parent of x, assigns it as parent
// for all the ancestors of x to avoid repeating the process
// a next time. This is just a Disjoint-set forest with
// flattening
// (http://en.wikipedia.org/wiki/Union_find#Disjoint-set_forests)
void toRoot(int *parent, int &x) {
int y = x;
while (parent[y] != y) {
y = parent[y];
}
while (x != y) {
int z = parent[x];
parent[x] = y;
x = z;
}
}
double determineLength(vector <int> cityX, vector <int> cityY,
vector <int> villageX, vector <int> villageY)
{
int vn = villageX.size();
int n = vn + 1;
// Make a custom graph with vn+1 nodes.
// The first vn nodes are villages.
// The last node is the conjunction of all cities.
// Cost to connect a village to the conjunction of all cities
// is equal to the minimum road between the village and any city.
set< pair<double, pair<int,int> > > edges;
for (int i=0; i<vn; i++) {
for (int j=0; j<i; j++) {
double dx, dy;
dx = villageX[i] - villageX[j];
dy = villageY[i] - villageY[j];
edges.insert( make_pair(sqrt(dx*dx + dy*dy), make_pair(i,j) ) );
}
double toCityCost = 1e100;
for (int j=0; j<cityX.size(); j++) {
double dx, dy;
dx = villageX[i] - cityX[j];
dy = villageY[i] - cityY[j];
toCityCost = std::min(toCityCost, sqrt(dx*dx+dy*dy) );
}
edges.insert( make_pair(toCityCost, make_pair(i,n-1) ) );
}
//
// Let us do Kruskal's algorithm on the custom modified graph.
// parent array for union algorithm
int parent[n];
for (int i=0; i<n; i++) {
parent[i] = i;
}
double total = 0;
// try all edges in ascending order of cost.
for_each( e, edges ) {
int u = e->second.first, v = e->second.second;
toRoot(parent,u);
toRoot(parent,v);
if ( u != v ) { //different sets, join them by
//adding the edge to the tree
parent[u] = v;
total += e->first;
}
}
return total;
}
};
No comments :
Post a Comment