pku 1830 开关问题（构造矩阵+高斯消元）

开关问题

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 4653	Accepted: 1675

Description

有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）

Input

输入第一行有一个数K，表示以下有K组测试数据。 

每组测试数据的格式如下： 

第一行 一个数N（0 < N < 29） 

第二行 N个0或者1的数，表示开始时N个开关状态。 

第三行 N个0或者1的数，表示操作结束后N个开关的状态。 

接下来 每行两个数I J，表示如果操作第 I 个开关，第J个开关的状态也会变化。每组数据以 0 0 结束。 

Output

如果有可行方法，输出总数，否则输出“Oh,it's impossible~!!” 不包括引号

Sample Input

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

Sample Output

4
Oh,it's impossible~!!
      

Hint

第一组数据的说明： 

一共以下四种方法： 

操作开关1 

操作开关2 

操作开关3 

操作开关1、2、3 （不记顺序） 

Source

[email protected]

题解：构造一个矩阵，利用增广矩阵化成行阶梯阵，然后判断是否有解，该题是01矩阵，“无穷解的情况”也是有穷种情况的，附上高斯消元的步骤和判断

首先，先介绍程序中高斯消元法的步骤：

(我们设方程组中方程的个数为equ，变元的个数为var，注意：一般情况下是n个方程，n个变元，但是有些题目就故意让方程数与变元数不同)

1. 把方程组转换成增广矩阵。

2. 利用初等行变换来把增广矩阵转换成行阶梯阵。

枚举k从0到equ – 1，当前处理的列为col(初始为0) ，每次找第k行以下(包括第k行)，col列中元素绝对值最大的列与第k行交换。如果col列中的元素全为0，那么则处理col + 1列，k不变。

3. 转换为行阶梯阵，判断解的情况。

① 无解

当方程中出现(0, 0, …, 0, a)的形式，且a != 0时，说明是无解的。

② 唯一解

条件是k = equ，即行阶梯阵形成了严格的上三角阵。利用回代逐一求出解集。

③ 无穷解。

条件是k < equ，即不能形成严格的上三角形，自由变元的个数即为equ – k，但有些题目要求判断哪些变元是不缺定的。

#include<stdio.h>
#include<string.h>
int a[33][33],n;
int gauss()
{
    int i,j,k,t,temp;

    for(i=j=1;i<=n&&j<=n;j++)
    {
        for(k=j;k<=n;k++) if(a[k][j]) break;
        if(a[k][j])
        {
            for(t=1;t<=n+1;t++)
                temp=a[i][t],a[i][t]=a[k][t],a[k][t]=temp;
            for(t=1;t<=n;t++)
            {
                if(t!=i&&a[t][j])
                    for(k=1;k<=n+1;k++)
                    a[t][k]^=a[i][k];
            }
            i++;
        }
    }
    for(k=i;k<=n;k++) if(a[k][n+1]) return -1;
    return 1<<(n-(i-1));
}
int main()
{
    int t,i,x,y,res;

    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(i=1;i<=n;i++) scanf("%d",&a[i][n+1]);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&x);
            a[i][n+1]^=x,a[i][i]=1;
        }
        while(scanf("%d%d",&x,&y),x&&y) a[y][x]=1;
        res=gauss();
        if(res==-1) printf("Oh,it's impossible~!!\n");
        else printf("%d\n",res);
    }

    return 0;
}