POJ1830 开关问题

前言

头一道高斯消元题啊…感觉这些东西建出模型基本上都是模板了…

题目描述

分析

这题建模难度不大。
我们设x_1,x_2,…,x_n分别表示开关1,2,…,n的操作次数,因为每个开关至多被操作1次,因此x_i只可能为1或0.令一个系数矩阵A来表示开关之间的关系,设A_{i,j}表示第j个开关是否影响第i个开关,若是则为1,若不是则为0.列向量B表示最终状态和开始状态的异或(事实上它的意义是开始状态到最终状态是否要变化).这样我们就得到模2意义下的同余方程组Ax=B.再用异或进行高斯消元即可。
如果发现自由变量有m个,那么答案就是2^m(自由变量01任取).

核心代码

int main() {
    scanf("%d", &K);
    while (K--) {
        scanf("%d", &N);
        memset(A, 0, sizeof A);
        for (int i = 0; i < N; i++) {
            scanf("%d", &A[i][N]);
            A[i][i] = 1;    // 别忘了自己和自己是一定有关联的
        }
        for (int i = 0, fnl; i < N; i++) {
            scanf("%d", &fnl);
            A[i][N] = (fnl - A[i][N] + 2) & 1;
        }
        for (int i, j; ~scanf("%d%d", &i, &j) && i && j; ) A[--j][--i] = 1; // 根据题意,关联关系应该是单向的
        solve();
    }
    return 0;
}

void solve() {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        int r = i;
        for (int j = i; j < N; j++)
            if (A[j][i]) { r = j; break; }
        if (A[r][i]) {
            if (r != i) {
                for (int j = i; j <= N; j++) std::swap(A[i][j], A[r][j]);
            }
            for (int j = i + 1; j < N; j++)
                if (A[j][i]) {
                    for (int k = i; k <= N; k++) A[j][k] ^= A[i][k];    // 模2同余方程组可以直接异或消元
                }
        }
        else {
            if (A[i][N]) return (void)puts("Oh,it's impossible~!!");   // 注意判断是否存在矛盾方程(矛盾方程消元后前面系数均会为0)
            ++cnt;  // 统计自由变量个数
        }
    }
    printf("%d\n", 1 << cnt);   // 答案即2的自由变量个数次幂
}

总结

高斯消元问题的重点在于建模。题中这类模2意义下的同余方程组算是代码实现最简单的一类了,直接异或消元即可。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注