POJ1830高消

開關問題

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 4088		Accepted: 1433

有N個相同的開關，每個開關都與某些開關有著聯係，每當你打開或者關閉某個開關的時候，其他的與此開關相關聯的開關也會相應地發生變化，即這些相聯係的開關的狀態如果原來為開就變為關，如果為關就變為開。你的目標是經過若幹次開關操作後使得最後N個開關達到一個特定的狀態。對於任意一個開關，最多隻能進行一次開關操作。你的任務是，計算有多少種可以達到指定狀態的方法。（不計開關操作的順序）

輸入第一行有一個數K，表示以下有K組測試數據。 
每組測試數據的格式如下： 
第一行 一個數N（0 < N < 29） 
第二行 N個0或者1的數，表示開始時N個開關狀態。 
第三行 N個0或者1的數，表示操作結束後N個開關的狀態。 
接下來 每行兩個數I J，表示如果操作第 I 個開關，第J個開關的狀態也會變化。每組數據以 0 0 結束。 

如果有可行方法，輸出總數，否則輸出“Oh,it's impossible~!!” 不包括引號

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

4
Oh,it's impossible~!!

第一組數據的說明： 
一共以下四種方法： 
操作開關1 
操作開關2 
操作開關3 
操作開關1、2、3 （不記順序） 

LIANGLIANG@POJ

題解：
簡單的高斯消元 詳細參見POJ1222 點擊打開鏈接poj1222
這題比起POJ1222簡單了 少了自己構造矩陣的過程 
各個開關的聯係已經告訴

關係要注意逆向推出相關性

即代碼

while(cin>>s1>>s2&&s1&&s2)

a[s2-1][s1-1]=1;

而不是

while(cin>>s1>>s2&&s1&&s2)

a[s1-1][s2-1]=1;

按照題意來即可

#include <iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=230;
int a[maxn][maxn+1],x[maxn];//a 是係數矩陣和增廣矩陣，x 是最後存放的解
// a[][maxn]中存放的是方程右麵的值（bi）
int equ,var;//equ 是係數陣的行數，var 是係數矩陣的列數（變量的個數）
int free_num,ans=100000000;

int abs1(int num) //取絕對值
{
    if (num>=0) return num;
    else
        return -1*num;
}
void Debug(void)
{
    int i, j;
    for (i = 0; i < equ; i++)
    {
        for (j = 0; j < var + 1; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
//調試輸出，看消元後的矩陣值，提交時，就不用了
inline int gcd(int a, int b) //最大公約數
{
    int t;
    while (b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

inline int lcm(int a, int b) //最小公倍數
{
    return a * b / gcd(a, b);
}

int dfs(int p) //枚舉自由解，隻能取0-1，枚舉完就回帶，找到最小的
{
    if (p<=free_num-1) //深入到了主對角線元素非0 的行了
    {
        //下麵就是回帶的代碼啊
        for(int i = free_num-1; i >= 0; --i)
        {
            int tmp = a[i][var] % 2;
            for(int j = i+1; j < var; ++j) //x[i]取決於x[i+1]--x[var]啊，所以後麵的解對前麵的解有影
//響。
                if(a[i][j] != 0)
                    tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
            x[i] = (tmp/a[i][i]) % 2; //上麵的正常解
        } //回帶完成了
//計算解元素為1 的個數；
        int sum=0;
        for(int i=0; i<var; i++) sum+=x[i];
        if (ans>sum) ans=sum;
        return 0;
    }
    x[p]=0;
    dfs(p-1);
    x[p]=1;
    dfs(p-1);
}
void swap(int &a,int &b)
{
    int temp=a;    //交換 2 個數
    a=b;
    b=temp;
}
long long Gauss()
{
    int k,col = 0;
//當前處理的列
    for(k = 0; k < equ && col < var; ++k,++col)
    {
        int max_r = k;
        for(int i = k+1; i < equ; ++i)
            if(a[i][col] > a[max_r][col])
                max_r = i;
        if(max_r != k)
        {
            for(int i = k; i < var + 1; ++i)
                swap(a[k][i],a[max_r][i]);
        }
        if(a[k][col] == 0)
        {
            k--;
            continue;
        }
        for(int i = k+1; i < equ; ++i)
        {
            if(a[i][col] != 0)
            {
                int LCM = lcm(a[i][col],a[k][col]);
                int ta = LCM/a[i][col], tb = LCM/a[k][col];
                if(a[i][col]*a[k][col] < 0)
                    tb = -tb;
                for(int j = col; j < var + 1; ++j)
                    a[i][j] = ( (a[i][j]*ta)%2 - (a[k][j]*tb)%2 + 2 ) % 2;
                // 0 和 1 兩種狀態
            }
        }
    }
//a[i][j]隻有

//上述代碼是消元的過程，行消元完成
//解下來 2 行，判斷是否無解
//注意 K 的值，k 代表係數矩陣值都為 0 的那些行的第 1 行
    for(int i = k; i < equ; ++i)
        if(a[i][col] != 0)
            return -1;
//Debug();

//唯一解或者無窮解,k<=var
//var-k==0 唯一解；var-k>0 無窮多解，自由解的個數=var-k
//能執行到這，說明肯定有解了，無非是 1 個和無窮解的問題。
//下麵這幾行很重要，保證秩內每行主元非 0，且按對角線順序排列，就是檢查列
    for(int i = 0; i <equ; ++i)//每一行主元素化為非零
        if(!a[i][i])
        {
            int j;
            for(j = i+1; j<var; ++j)
                if(a[i][j])
                    break;
            if(j == var)
                break;
            for(int k = 0; k < equ; ++k)
                swap(a[k][i],a[k][j]);
        }
// ----處理保證對角線主元非 0 且順序，檢查列完成

    free_num=k;
    if (var-k>0)
    {
        return (__int64)pow(double(2),double(var-k));
    }
    if(var-k<0)
        return -1;
// 無解返回 -1
    if (var-k==0)//唯一解時
    {
        return 1;


    }
}


int main()
{
    int n,t,m1[30],m2[30],s1,s2;
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(x,0,sizeof(x));
        cin>>n;
        var=equ=n;
        for(int i=0; i<n ; i++)
            cin>>m1[i];
        for(int j=0; j<n; j++)
        {
            cin>>m2[j];
            if(m2[j]!=m1[j])
                a[j][n]=1;
            a[j][j]=1;
        }
        while(cin>>s1>>s2&&s1&&s2)
            a[s2-1][s1-1]=1;
        //  Debug();
        long long j1=Gauss();
        //  Debug();
        if(j1==-1)
            cout<<"Oh,it's impossible~!!"<<endl;
        else
            cout<<j1<<endl;

    }
    return 0;
}