POJ 2345 異或線性方程組 + 高斯消元

題意

傳送門 POJ 2345

題解

設 t e c h n i c i a n s technicians technicians 為 x j x_{j} xj​， v a l v e s valves valves 為 b i b_{i} bi​， x j x_{j} xj​ 是否管理 b i b_{i} bi​ 對應系數為 a i , j a_{i,j} ai,j​，則有

{ a 0 , 0 x 0 ⊕ a 0 , 1 x 1 ⊕ ⋯ ⊕ a 0 , n − 1 = b 0 … a n − 1 , 0 x 0 ⊕ a n − 1 , 1 x 1 ⊕ ⋯ ⊕ a n − 1 , n − 1 = b n − 1 \begin{cases} a_{0,0}x_{0}\oplus a_{0,1}x_{1}\oplus \dots \oplus a_{0,n-1}=b_{0}\\ \dots \\ a_{n-1,0}x_{0}\oplus a_{n-1,1}x_{1}\oplus \dots \oplus a_{n-1,n-1}=b_{n-1} \end{cases} ⎩⎪⎨⎪⎧​a0,0​x0​⊕a0,1​x1​⊕⋯⊕a0,n−1​=b0​…an−1,0​x0​⊕an−1,1​x1​⊕⋯⊕an−1,n−1​=bn−1​​

高斯消元時，考慮到 v a l v e s valves valves 類似開關的性質，聯立的方程間也使用異或運算。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define abs(x) ((x) < 0 ? -(x) : (x))
#define INF 0x3f3f3f3f3f3f3f3f
#define delta 0.85
using namespace std;

#define maxn 255
int N;
bool charge[maxn][maxn];

typedef vector<int> vec;
typedef vector<vec> mat;
// 列主高斯消元法, 求解 Ax = b
// 當方程組無解或有無窮多解時, 傳回一個長度為 0 的數組
vec gauss_jordan(const mat &A, const vec &b)
{
    int n = A.size();
    mat B(n, vec(n + 1));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            B[i][j] = A[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        B[i][n] = b[i];
    }
    for (int i = 0; i < n; i++)
    {
        int pivot = i;
        for (int j = i; j < n; j++)
        {
            if (B[j][i] == 1)
            {
                pivot = j;
                break;
            }
        }
        swap(B[i], B[pivot]);
        if (B[i][i] == 0)
            return vec();
        for (int j = 0; j < n; j++)
        {
            if (i != j)
            {
                for (int k = i + 1; k <= n; k++)
                    B[j][k] ^= B[j][i] * B[i][k];
            }
        }
    }
    vec x(n);
    for (int i = 0; i < n; i++)
        x[i] = B[i][n];
    return x;
}

void solve()
{
    mat A(N, vec(N, 0));
    vec b(N, 0);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (charge[i][j])
            {
                A[j][i] = 1;
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        b[i] = 1;
    }
    vec res = gauss_jordan(A, b);
    if (res.size() == 0)
    {
        puts("No solution\n");
        return;
    }
    for (int i = 0; i < N; i++)
    {
        if (res[i])
        {
            printf("%d ", i + 1);
        }
    }
    putchar('\n');
}

int main()
{
    while (~scanf("%d", &N))
    {
        memset(charge, 0, sizeof(charge));
        for (int i = 0; i < N; i++)
        {
            int v;
            while (~scanf("%d", &v) && v != -1)
            {
                charge[i][v - 1] = 1;
            }
        }
        solve();
    }
    return 0;
}