题目链接: http://poj.org/problem?id=1830
题目可以看作求以x0~xn-1为自变量,以y0~yn-1(初始到最终状态的改变情况,如果变化为1,否则0)为变量的议程组,如果yj 受 xi开关的控制,则其系数为一,题解就转化为求
方程解的问题,采用高斯消元法解决。
#include<stdio.h> #include<string.h> #define M 32 int mat[M][M]; int a[M],n; int Encode(int a[],int l) { int r,i; for(r=i=0;i<l;i++){ r<<=1; r+=a[i]; } return r; } int Gauss() { int r,i,j,k,p; for(i=0;i<n;i++){ j=i; for(k=i+1;k<n;k++){ if(Encode(mat[k],n+1)>Encode(mat[j],n+1)) j=k; } if(j!=i){ for(k=0;k<=n;k++) r=mat[i][k],mat[i][k]=mat[j][k],mat[j][k]=r; } for(p=0;p<=n&&!mat[i][p];p++); if(mat[i][p]){ for(j=i+1;j<n;j++){ if(mat[j][p]){ for(k=p;k<=n;k++) mat[j][k]=(mat[j][k]+mat[i][k])&1; } } } else break; } r=1; for(i=n-1;i>=0&&r;i--){ for(j=0;j<n&&!mat[i][j];j++); if(j<n) break; if(mat[i][j]) r=0; else r++; } return r; } int main() { int t,x,y,i; scanf("%d",&t); while(t--){ scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",a+i); memset(mat,0,sizeof(mat)); for(i=0;i<n;i++){ scanf("%d",&x); if(x!=a[i]) mat[i][n]=1; mat[i][i]=1; } while(scanf("%d%d",&y,&x),x|y) mat[x-1][y-1]=1; x=Gauss(); printf(x?"%d\n":"Oh,it's impossible~!!\n",1<<(x-1)); } return 0; }