ACM Solution to the 2012 Europe 'kingdom bankruptcy' problem
#include <iostream> | |
#include <vector> | |
#include <bitset> | |
#include <set> | |
using namespace std; | |
#define LOG_LEVEL 0 | |
#define DEBUG(s) { \ | |
if (LOG_LEVEL) { std::cerr << s << endl; } \ | |
} | |
const int MAX_K = 20; | |
vector<vector<int> > debtMatrix; | |
bitset<MAX_K> reachable; | |
bitset<MAX_K> bankrupt; | |
set<unsigned long> visited; | |
bool isBankrupt (int kingdom, int n) { | |
int score = 0; | |
for (int i = 0; i < n; i++) { | |
if (! bankrupt[i]) { | |
score += debtMatrix[i][kingdom]; | |
} | |
} | |
return score < 0; | |
} | |
/** | |
* Count is the number of bits flipped | |
*/ | |
void DFS(int count, int n) { | |
visited.insert(bankrupt.to_ulong()); | |
if (count == n - 1) { | |
// find the last kingdom standing | |
for (int i = 0; i < n; i++) { | |
if (! bankrupt[i]) { | |
reachable[i] = 1; | |
break; | |
} | |
} | |
return; | |
} | |
for (int i = 0; i < n; i++) { | |
if (! bankrupt[i] && isBankrupt(i, n)) { | |
bankrupt[i] = 1; | |
// make sure that we haven't explored this route before | |
if (visited.find(bankrupt.to_ulong()) == visited.end()) { | |
DFS(count + 1, n); | |
} | |
// undo the op | |
bankrupt[i] = 0; | |
} | |
} | |
} | |
int main() { | |
cin.sync_with_stdio(false); | |
cout.sync_with_stdio(false); | |
cerr.sync_with_stdio(false); | |
int T; | |
cin >> T; | |
int n, tmp; | |
for (int t = 0; t < T; t++) { | |
cin >> n; | |
debtMatrix.clear(); | |
reachable.reset(); | |
visited.clear(); | |
bankrupt.reset(); | |
for (int i = 0; i < n; i++) { | |
vector<int> debtRow (n); | |
for (int k = 0; k < n; k++) { | |
cin >> debtRow[k]; | |
} | |
debtMatrix.push_back(debtRow); | |
} | |
DFS(0, n); | |
DEBUG(visited.size()); | |
int j = 0; | |
//DEBUG("j"); | |
for (int i = 0; i < n; i++) { | |
if (reachable[i]) { | |
if (j > 0) cout << " "; | |
cout << (i + 1); | |
j++; | |
} | |
} | |
if (j == 0) { | |
cout << 0; | |
} | |
cout << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment