/* The country of Byteland contains N cities and N - 1
bidirectional roads between them such that there is a path between any two
cities. The cities are numbered (0,…,N - 1). The people were very unhappy about
the time it took to commute, especially salesmen who had to go about every city
selling goods. So it was decided that new roads would be built between any two
“somewhat near” cities. Any two cities in Bytleland that can be reached by
traveling on exactly two old roads are known as “somewhat near” each other. Now
a salesman situated in city 0, just like any other typical salesman, has to
visit all cities exactly once and return back to city 0 in the end. In how many
ways can he do this? */
My approach is not quite good (it only works on local computer, but didn't pass all the test cases from online judge), because i use dynamic programming and time complexity is exponential.
Also I've searched online for better approaches. This one has a better performance, but it requires certain math background to come up with this solution. Here is the link:
#include <iostream>
#include <vector>
#include <set>
using namespace std;
class ByteLand{
public:
ByteLand(int);
~ByteLand();
int
calculateWays();
private:
void buildOldPath(int, int);
void
buildNewPath();
void findPath(int, int);
private:
int numCity;
int * distance;
bool * visited;
int ways;
};
ByteLand::ByteLand(int n) : numCity(n), ways(0) {
distance = new int[numCity * numCity];
for (int i = 0; i < numCity; ++i) {
for (int j = 0; j < numCity; ++j) {
if (i == j) {
distance[i*numCity+j] = 0;
} else {
distance[i*numCity+j] = numCity;
}
}
}
for (int i = 0; i < numCity-1; ++i) {
int a, b;
cin >> a
>> b;
buildOldPath(a, b);
}
buildNewPath();
}
ByteLand::~ByteLand() {
delete [] distance;
}
void ByteLand::buildOldPath(int a, int b) {
distance[a*numCity+b] = 1;
distance[b*numCity+a] = 1;
}
void ByteLand::buildNewPath() {
for (int i = 0; i < numCity; ++i) {
for (int j = 0; j < numCity; ++j) {
if (distance[i*numCity+j] == 1) {
for (int k = 0; k < numCity; ++k) {
if (k != i
&& distance[j*numCity+k] == 1) {
distance[i*numCity+k] = 2;
}
}
}
}
}
}
int ByteLand::calculateWays() {
visited = new bool[numCity];
findPath(0, 0);
delete [] visited;
return ways;
}
void ByteLand::findPath(int current, int numVisited) {
if (current == 0 &&
numVisited == numCity) {
ways++;
return;
}
if (current == 0 &&
numVisited > 0) {
return;
}
for (int i = 0; i < numCity; ++i) {
if (!visited[i] &&
(distance[i*numCity+current] == 1 || distance[i*numCity+current] == 2)) {
visited[i] = true;
findPath(i,
numVisited+1);
visited[i] = false;
}
}
}
No comments:
Post a Comment