poj 1830 開關問題，poj1830
開關問題
題意:給n(0 < n < 29)開關的初始和最終狀態(01表示)，以及開關之間的關聯關系(關聯關系是單向的輸入a b表示a->b)，問有幾種方式得到最終的狀態。否則輸出字符字面值。
1.與poj 1222的區別:關聯為單向，需要預處理出每個開關對自己的關聯(開始在輸入關聯關系中處理自身的關聯，WA了兩發)，操作的矩陣(變換的矩陣)為初始狀態XOR最終狀態；
2.處理完之後判斷系數全為0的最終結果a[k][var]是否為0來判斷是否無解。同時如有n個自由變元，由於每個變元只有兩種狀態，所以只有2^n個方案。
![]()
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
int a[35][35];
int equ,var;
int x[35];
void debug()
{
int i,j;
rep0(i,0,equ){
rep1(j,0,var)
cout<<a[i][j]<<" ";
cout<<endl;
}
}
int Guass()
{
int i,j,k,free_var = 0,row,col;
for(row = 0,col = 0;row < equ && col < var;row++,col++){
int mx = row;
rep0(j,row+1,equ)
if(abs(a[j][col]) > abs(a[mx][col])) mx = j;
if(a[mx][col] == 0){
row--; // 行不變；
free_var++;
continue;
}
if(mx != row)
rep1(k,col,var)
swap(a[row][k],a[mx][k]);
rep0(j,row+1,equ){
if(a[j][col]){ //第j盞燈也會對第i盞燈產生影響
rep1(k,col,var)
a[j][k] ^= a[row][k];
}
}
}
//debug();
for(;row < equ;row++)if(a[row][var] != 0) return -1; //無解；
if(free_var != 0) return free_var;
rep_1(i,var-1,0){ //求解的變量的個數，並不是方程的個數；
x[i] = a[i][var];
rep0(j,i+1,equ)
x[i] ^= (a[i][j] && x[j]); //第j個燈會影響到第i盞燈，同時第j盞燈也會亮。
}
return 0;
}
void init()
{
int i,j,k,n;
MS0(a);MS0(x);
scanf("%d",&n);
equ = var = n;
int x,l,r;
rep0(i,0,n) scanf("%d",&a[i][n]);
rep0(i,0,n) scanf("%d",&x),a[i][n] ^= x;
rep0(i,0,n) a[i][i] = 1; //沒有關聯要格外賦值；
while(scanf("%d %d",&l,&r) == 2 && l+r){
a[r-1][l-1] = 1;
}
}
int main()
{
int T,kase = 1,i;
cin>>T;
while(T--){
init();
int ret = Guass();
if(ret == -1) puts("Oh,it's impossible~!!");
else printf("%d\n",1<<ret);
}
return 0;
}
View Code
