poj 1830(高斯消元)

poj 1830(高斯消元)

開關問題 Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 5771 Accepted: 2172

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

LIANGLIANG@POJ

AC代碼：

解方程，求出自由元的個數即可！

#include
#include
using namespace std;
int a[32][32];
int n;
int gauss_elimination(){
    int i=0,j=0,k,r,u;
    while(i>T;
    while(T--){
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i=0;i>a[i][n];
        for(int i=0;i>x;
            a[i][i]=1;
            a[i][n]^=x;
        }
        int x,y;
        while(cin>>x>>y){
            if(x==0 && y==0)
                break;
            a[y-1][x-1]=1;
        }
        int ans=gauss_elimination();
        if(ans==-1)
            cout<<"Oh,it's impossible~!!"<