USACO 1.3 Wormholes

The problem can be reduced to two sub problems:

• Generate all combinations of pairs. This can be solved using backtrack.
• For each combination test if there is a cycle. This can be solved by exhaustive search: starting from each wormhole, and try move the number of total wormholes, and repeat, until all wormholes are tested.

#include <iostream>
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

const int kMaxHoles = 12;
int total;
vector<int> vx(kMaxHoles + 1, 0);
vector<int> vy(kMaxHoles + 1, 0);
vector<int> nextWormhole(kMaxHoles + 1, 0);
vector<int> vpair(kMaxHoles + 1, 0);
vector<bool> visited(kMaxHoles + 1, false);

bool hasCycle() {
  for (int start = 1; start <= total; ++start){
    int current = start;
    for (int move = 1; move <= total; ++move)
      current = nextWormhole[vpair[current]];
    if (current != 0)
      return true;
  }
  return false;
}

int backtrack(){
  int unpaired = 0;
  for (int i = 1; i <= total; ++i) {
    if (vpair[i] == 0){
      unpaired = i;
      break;
    }
  }

  if (unpaired == 0) {
    return hasCycle();
  }

  int result = 0;
  for (int topair = unpaired + 1; topair <= total; ++topair)
    if (vpair[topair]  == 0){
      vpair[unpaired] = topair;
      vpair[topair] = unpaired;
      result += backtrack();
      vpair[unpaired] = 0;
      vpair[topair] = 0;
    }
  return result;
}

int main(){
  ifstream fin("wormhole.in");
  ofstream fout("wormhole.out");

  fin >> total;
  cout << total << endl;
  for (int i = 1; i <= total; ++i) {
    fin >> vx[i] >> vy[i];
    cout << vx[i] << " " << vy[i] << endl;
  }

  int current, next;
  for (current = 1; current <= total; ++current) {
    for (next = 1; next <= total; ++next){
      if (vy[current] != vy[next] || vx[next] <= vx[current]) {
        continue;
      }
      if (nextWormhole[current] == 0 || vx[next] < vx[nextWormhole[current]]) {
        cout << "current : " << current << "; next : " << next << endl;
        nextWormhole[current] = next;
      }
    }
  }

  for (int i = 1; i <= 12; ++i) {
    cout << nextWormhole[i] << ";";
  }

  fout << backtrack() << endl;
  return 0;
}