Advertisement
Guest User

Untitled

a guest
May 27th, 2015
233
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. /*
  2. ID: lisa.va1
  3. PROG: test
  4. LANG: C++11
  5. */
  6. #include <cstdio>
  7. #include <iostream>
  8. #include <fstream>
  9. #include <cmath>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <set>
  13. #include <map>
  14. #include <queue>
  15. #include <stack>
  16. #include <cstdlib>
  17.  
  18. using namespace std;
  19.  
  20. #define rep(i, a, b) for(int i = (a); i < int(b); ++i)
  21. #define trav(it, v) for(auto it = (v).begin(); it != (v).end(); ++it)
  22.  
  23. typedef vector<int> vi;
  24. typedef vector<vi> vii;
  25. typedef pair<int, int> pii;
  26. typedef long long ll;
  27.  
  28. int n;
  29.  
  30. vector<bool> ans;
  31.  
  32. vector<vector<ll> > debt;
  33. vector<bool> seen;
  34.  
  35. //seems to work
  36. ll calc (int i, int a) {
  37.     ll cur = 0;
  38.     rep(j, 0, n) {
  39.         if((a& (1<<j))) cur+= debt[i][j]; //om vi inte tagit bort j än ska skulden adderas
  40.     }
  41.     return cur;
  42. }
  43. void dp(int a) {
  44.     //cout << a << endl;
  45.     if(seen[a]) return;
  46.     rep(i, 0, n) {
  47.         if((a & (1<<i))) {
  48.             ll cur = calc(i, a);
  49.             if(cur > 0) {
  50.                 dp(a^(1<<i));
  51.             }
  52.             if(((a^(1<<i)) == 0) && cur == 0) ans[i] = true;
  53.         }
  54.     }
  55.     seen[a] = true;
  56. }
  57.  
  58. int main(){
  59.     int t;
  60.     cin >> t;
  61.     rep(k, 0, t) {
  62.         cin >> n;
  63.         debt.assign(n, vector<ll>(n));
  64.         ans.assign(n, false);
  65.         seen.assign((1<<n), false);
  66.         rep(i, 0, n) {
  67.             rep(j, 0, n) {
  68.                 cin >> debt[i][j];
  69.             }
  70.         }
  71.         dp((1<<n)-1);
  72.         bool cool = false;
  73.         rep(i, 0, n) {
  74.             if(ans[i])  {
  75.                 cout << i+1 << " ";
  76.                 cool = true;
  77.             }
  78.         }
  79.         if(!cool) cout << 0;
  80.         cout << endl;
  81.     }
  82.     return 0;
  83. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement