Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: lisa.va1
- PROG: test
- LANG: C++11
- */
- #include <cstdio>
- #include <iostream>
- #include <fstream>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <queue>
- #include <stack>
- #include <cstdlib>
- using namespace std;
- #define rep(i, a, b) for(int i = (a); i < int(b); ++i)
- #define trav(it, v) for(auto it = (v).begin(); it != (v).end(); ++it)
- typedef vector<int> vi;
- typedef vector<vi> vii;
- typedef pair<int, int> pii;
- typedef long long ll;
- int n;
- vector<bool> ans;
- vector<vector<ll> > debt;
- vector<bool> seen;
- //seems to work
- ll calc (int i, int a) {
- ll cur = 0;
- rep(j, 0, n) {
- if((a& (1<<j))) cur+= debt[i][j]; //om vi inte tagit bort j än ska skulden adderas
- }
- return cur;
- }
- void dp(int a) {
- //cout << a << endl;
- if(seen[a]) return;
- rep(i, 0, n) {
- if((a & (1<<i))) {
- ll cur = calc(i, a);
- if(cur > 0) {
- dp(a^(1<<i));
- }
- if(((a^(1<<i)) == 0) && cur == 0) ans[i] = true;
- }
- }
- seen[a] = true;
- }
- int main(){
- int t;
- cin >> t;
- rep(k, 0, t) {
- cin >> n;
- debt.assign(n, vector<ll>(n));
- ans.assign(n, false);
- seen.assign((1<<n), false);
- rep(i, 0, n) {
- rep(j, 0, n) {
- cin >> debt[i][j];
- }
- }
- dp((1<<n)-1);
- bool cool = false;
- rep(i, 0, n) {
- if(ans[i]) {
- cout << i+1 << " ";
- cool = true;
- }
- }
- if(!cool) cout << 0;
- cout << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement