POJ1830 开关问题高斯消元

这题是给定N个灯的初始和最终状态，再给定一些关系，这些关系说明按某个开关可能影响其他的灯的开关情况，可以将这种关系视为一种取反的关系。

对于这题我们假设一组数据：

3
0 1 0
1 1 0
1 2
2 3
1 3
3 2
0 0

对于以上的数据，我们用矩阵来表示整个操作的过程和状态

　　　0　　　　　　　1

S = 1 E = 1

　　　0　　　　　　 0

我们可以很显然的知道，某个等的亮灭情况将体现出各个开关的复合结果，因此我们可以得到这样的方程组，模二加等价于异或操作：

E(a) = xa*A11 ^ xb*A12 ^ xc*A13 ^ S(a);

E(b) = xa*A21 ^ xb*A22 ^ xc*A23 ^ S(b);

E(c) = xa*A31 ^ xb*A32 ^ xc*A33 ^ S(c);

其中S(a)表示初始状态，E(a)表示a号灯最终的情况，xa表示a号开关是否按下，A13表示3号开关是否影响1号灯的亮灭，异或操作体现了操作的具体影响。

将S项移到方程的左边，我们抽象出系数矩阵，然后构造出增广矩阵，然后就是进行高斯消元，高斯消元的意思可以看作是符合一系列两个逻辑关系的情况下，对变元要求的变换。只不过这里用的全部都是异或操作，最后我们进行秩的判定，如果矩阵的秩和邻接矩阵的秩不相等的话那么就无解，如果相同的话，那么说明达到理想灯的亮灭情况下至少需要确定的状态的开关数为矩阵的秩。那么解就是剩下开关的任意选择了，即2^X（每个开关对应关或者是开）。

代码如下：

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int N, s[50], e[50];

void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

struct Matrix
{
    int a[50][50];    
    void rswap(int x, int y)
    {
        for (int j = 1; j <= N+1; ++j) {
            swap(a[x][j], a[y][j]);  
        }
    }
    void relax(int x, int y) 
    {
        for (int j = 1; j <= N+1; ++j) {
            a[y][j] ^= a[x][j];
        }
    }
    void init(){
        memset(a, 0, sizeof (a));
        for (int i = 1; i <= N; ++i) {
            a[i][i] = 1;
        }
    }
}M;

void Gauss()
{
    int ptr, t, i, j;
    for (i = 1, j = 1; i <= N, j <= N; ++i, ++j) {
        for (ptr = i; ptr <= N; ++ptr) {
            if (M.a[ptr][j]) {
                // 当第i行的j列不为零
                break;
            }
        }
        if (ptr == N+1) {
            --i;
            continue;
        }
        if (ptr != i) {
            M.rswap(ptr, i);
        }
        for (int k = i + 1; k <= N; ++k) {
            if (!M.a[k][j]) {
                continue;
            }
            M.relax(i, k);
        }
    }
    for (int k = i; k <= N; ++k) {
        if (M.a[k][N+1] != 0) {
            puts("Oh,it's impossible~!!");
            return;
        }
    }
    printf("%d\n", 1<<(N-i+1));
}

int main()
{
    int T, a, b;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        M.init();
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &s[i]);
        }
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &e[i]);
            M.a[i][N+1] = s[i]^e[i];
        }
        while (scanf("%d %d", &a, &b), a | b) {
            M.a[b][a] = 1;
        }
        Gauss();
    }
    return 0;
}

POJ1830 开关问题 高斯消元

POJ1830 开关问题高斯消元