P3429 [POI2005] DWA - Two Parties 题解

1
#include <bits/stdc++.h>
2
#define N 210
3
using namespace std;
4

5
bitset<N> matrix[N];
6
bitset<N> ans;
7
int n;
8

9
void out() {
10
    cerr << "-----------------" << endl;
11
    for (int i = 1; i <= n; i++) {
12
        for (int j = 1; j <= n + 1; j++) {
13
            cerr << setw(5) << matrix[i][j];
14
        }
15
        cerr << endl;
16
    }
17
    cerr << "-----------------" << endl;
18
}
19

20
int gauss() {
21
    int rank = 0;
22
    for (int c = 1, r = 1; c <= n; c++) {
23
        int t = r;
24
        for (int i = r; i <= n; i++) {
25
            if (matrix[i].test(c)) {
26
                t = i;
27
                break;
28
            }
29
        }
30
        if (!matrix[t].test(c)) continue;
31
        if (t ^ r) swap(matrix[r], matrix[t]);
32

33
        for (int i = 1; i <= n; i++) {
34
            if (matrix[i].test(c) && i ^ r) {
35
                matrix[i] ^= matrix[r];
36
            }
37
        }
38
        r++;
39
        rank++;
40
    }
41
    if (rank < n) {
42
        for (int i = rank + 1; i <= n; i++) {
43
            if (matrix[i].test(n + 1)) return 0;
44
        }
45
        for (int i = 1; i <= n; i++) {
46
            for (int j = 1; j <= n + 1; j++) {
47
                if (matrix[i].test(j)) {
48
                    ans[j] = matrix[i][n + 1];
49
                    break;
50
                }
51
            }
52
        }
53
        return 1;
54
    }
55
    for (int i = 1; i <= n; i++) ans[i] = matrix[i][n + 1];
56
    return 2;
57
}
58

59
int main() {
60
    ios::sync_with_stdio(false);
61
    cin.tie(nullptr);
62
    cout.tie(nullptr);
63

64
    cin >> n;
65
    for (int i = 1; i <= n; i++) {
66
        int k;
67
        cin >> k;
68
        if (k & 1) matrix[i].flip(i);
69
        matrix[i][n + 1] = k & 1;
70
        while (k--) {
71
            int x;
72
            cin >> x;
73
            matrix[i].flip(x);
74
        }
75
    }
76
    int res = gauss();
77
    if (res) {
78
        cout << ans.count() << endl;
79
        for (int i = 1; i <= n; i++) {
80
            if (ans.test(i)) cout << i << ' ';
81
        }
82
    } else cout << "Impossible" << endl;
83
    return 0;
84
}