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;
}