现在的位置: 首页 > 综合 > 正文

poj 1830 开关问题(高斯消元)

2017年10月18日 ⁄ 综合 ⁄ 共 1876字 ⁄ 字号 评论关闭

终止状态是从初始状态由开关组合影响而形成的,那么就有一个等式使得初始状态可以到达终止状态,

例如a,b,c三个开关

E[a] = (xa * mp[a][a]) ^ (xb * mp[a][b]) ^ (xc*map[a][c]) ^ S[a]

E[b] = (xa * mp[b][a]) ^ (xb * mp[b][b]) ^ (xc*map[b][c]) ^ S[b]

E[c] = (xa * mp[c ][a]) ^ (xb * mp[c][b]) ^ (xc*map[c][c]) ^ S[c]

E数组为开关的终止状态(a,b,c为开关),S数组为开关的初始状态,mp[i][j] 代表j开关是否影响i开关。x为变元

根据上面的方程装换成高斯方程组

换成矩阵形式:

 mp[a][a]   mp[a][b]   map[a][c]    E[a ]^ S[a]

 mp[b][a]   mp[b][b]   map[b][c]    E[b] ^ S[b]

 mp[c ][a]   mp[c][b]   map[c][c]    E[c] ^ S[c ]

转换成行阶梯型矩阵,然后求出矩阵的秩,矩阵的秩即为不变元的个数,剩下的就是自由元的个数。

不变元就是,我们将开关由初始状态变为终止状态所必须要动的开关,而自由元就是我们不一定要动的开关。

因此,我们能到达终止状态的方案就是2的自由元次幂的个数,因为每个开关只有0,1两种状态。

注意求解是异或运算。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 50
int a[MAXN], e[MAXN];
int n;

void swap(int &a,int &b){
    int t = a;
    a = b;
    b = t;
}

struct Matrix{
    int mp[MAXN][MAXN];
    void rswap(int x,int y){//将x行的元素与y行的元素互换
        for(int j = 1; j <= n+1; j++){
            swap(mp[x][j],mp[y][j]);
        }
    }
    void relax(int x, int y){//用x行的元素消掉y行的元素,一般为第一个非零元
        for(int j = 1; j <= n+1; j ++){
            mp[y][j] ^= mp[x][j];
        }
    }
    void init(){//初始化
        memset(mp,0,sizeof(mp));
        for(int i = 1; i <= n ;i++){//自己可以改变自己
            mp[i][i] = 1;
        }
    }
}M;

void Gauss(){
    int i, j, k, ptr;
    for(i = 1, j= 1; j <= n; ++i, ++j){//形成行阶梯型矩阵,从第一行第一列开始,逐列递增
        for(ptr = i; ptr  <= n ; ptr++){//找出第一个是非零元的行
            if(M.mp[ptr][j]){
                break;
            }
        }
        if(ptr == n+1){//如果这一列所有行都是零元,则跳过这一列
            --i;
            continue;
        }
        if(ptr != i){//如果第一个是非零元的行不是当前行,则与其互换位置
            M.rswap(ptr,i);
        }
        for(k = i+1; k <= n; k++ ){//用当前的行当前列的值对下面所有行当前列的值进行消除,使其为0,以满足行阶梯型
            if(!M.mp[k][j]){//如果是0,则跳过
                continue;
            }
            M.relax(i,k);//不是,则消除。
        }
    }
    for( k = i; k <= n; k++){//处理完所有列(为n,n+1为答案列不用计算)之后,也就是现在mp数组就是行阶梯型了,那么看零行的答案是否都为0,有不为0,即是无解。
        if(M.mp[k][n+1] != 0){
            printf("Oh,it's impossible~!!\n");
            return ;
        }
    }

    printf("%d\n",1<<(n-i+1));//有多少零行就有多少自由元,输出结果
    return;
}


int main() {
    int Case , s, t;
    s =  1; t = 2;
    swap(s,t);
    scanf("%d",&Case);
    while(Case--){
        scanf("%d",&n);
        M.init();//初始化矩阵
        for(int i = 1; i <= n; i++){//初始状态读入
            scanf("%d",&a[i]);
        }
        for(int i = 1; i <= n; i++){//终止状态读入
            scanf("%d",&e[i]);
            M.mp[i][n+1] = a[i] ^ e[i];//增广矩阵
        }
        while(scanf("%d%d",&s,&t),s|t){//相互影响的开关读入
            M.mp[t][s] = 1;
        }
        Gauss();
    }
    return 0;
}

抱歉!评论已关闭.